algorithm - Complexity of the recursion: T(n) = T(n-1) + T(n-2) + C -

i want understand how arrive @ complexity of below recurrence relation.

t(n) = t(n-1) + t(n-2) + c given t(1) = c , t(2) = 2c;

generally equations t(n) = 2t(n/2) + c (given t(1) = c), use following method.

t(n) = 2t(n/2) + c => t(n) = 4t(n/4) + 3c => t(n) = 8t(n/8) + 7c => ... => t(n) = 2^k t (n/2^k) + (2^k - 1) c

now when n/2^k = 1 => k = log (n) (to base 2)

t(n) = n t(1) + (n-1)c      = (2n -1) c      = o(n)

but, i'm not able come similar approach problem have in question. please correct me if approach incorrect.

the complexity related input-size, each call produce binary-tree of calls

where t(n) make 2ⁿ calls in total ..

t(n) = t(n-1) + t(n-2) + c

t(n) = o(2^n-1) + o(2^n-2) + o(1)

o(2ⁿ)

in same fashion, can generalize recursive function, fibonacci number

t(n) = f(n) + ( c * 2ⁿ)

next can use direct formula instead of recursive way

using complex method known binet's formula

Live