Complexity of recursive Fibonacci algorithm

Question Detail: 

Using the following recursive Fibonacci algorithm:

def fib(n):    if n==0:       return 0    elif n==1       return 1    return (fib(n-1)+fib(n-2)) 

If I input the number 5 to find fib(5), I know this will output 5 but how do I examine the complexity of this algorithm? How do I calculate the steps involved?

Asked By : joker

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/14733

Answered By : ees_cu

Most of the times, you can represent the recursive algorithms using recursive equations. In this case the recursive equation for this algorithm is $T(n) = T(n-1) + T(n-2) + \Theta(1)$. Then you can find the closed form of the equation using the substitution method or the expansion method (or any other method used to solve recurrences). In this case you get $T(n) = \Theta(\phi^n)$, where $\phi$ is the golden ratio ($\phi = \frac{(1 + \sqrt{5})}{2}$).

If you want to find out more about how to solve recurrences I strongly recommend you to read chapter 4 of Introduction to Algorithms.