I want to understand how to arrive at the complexity of the below recurrence relation.
T(n) = T(n-1) + T(n-2) + C
Given T(1) = C
and T(2) = 2C;
Generally for equations like T(n) = 2T(n/2) + C
(Given T(1) = C), I use the 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 the base 2)
T(n) = n T(1) + (n-1)C
= (2n -1) C
= O(n)
But, I'm not able to come up with similar approach for the problem I have in question. Please correct me if my approach is incorrect.
The complexity is related to input-size, where each call produce a binary-tree of calls
Where T(n)
make 2
n
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
n
)
In the same fashion, you can generalize your recursive function, as a Fibonacci number
T(n) = F(n) + ( C * 2
n
)
Next you can use a direct formula instead of recursive way
Using a complex method known as Binet's Formula