12 views

What is the recurrence equation and how to solve it?

| 12 views
0
T(n) = T(n-1) + T(n-2) + c;

This is the recurrence for Fibonacci, which has an exponential running time.

$T(n)= \begin{Bmatrix} n & n<=1\\ T(n-1)+T(n-2) & n>1 \end{Bmatrix}$
You can make Tree.. And when you make tree, height  of tree will be $n$ in worst case(n-1) and there will be $O(2^n)$ leaf nodes. To get ans of $f(n)$ you  have to add all those leaf node and operation take constant time.
So, Time complexity of this function $O(2^n)$.