Why is the complexity of computing the Fibonacci series 2^n and not n^2?

algorithm recursion big-o fibonacci
Suri picture Suri · Sep 25, 2011 · Viewed 56.7k times · Source

I am trying to find complexity of Fibonacci series using a recursion tree and concluded height of tree = O(n) worst case, cost of each level = cn, hence complexity = n*n=n^2

How come it is O(2^n)?

Answer

amit picture amit · Sep 25, 2011

The complexity of a naive recursive fibonacci is indeed 2ⁿ.

T(n) = T(n-1) + T(n-2) = T(n-2) + T(n-3) + T(n-3) + T(n-4) = 
= T(n-3) + T(n-4) + T(n-4) + T(n-5) + T(n-4) + T(n-5) + T(n-5) + T(n-6) = ...

In each step you call T twice, thus will provide eventual asymptotic barrier of:
T(n) = 2⋅2⋅...⋅2 = 2ⁿ

bonus: The best theoretical implementation to fibonacci is actually a close formula, using the golden ratio: 

Fib(n) = (φⁿ – (–φ)⁻ⁿ)/sqrt(5) [where φ is the golden ratio]

(However, it suffers from precision errors in real life due to floating point arithmetics, which are not exact)

Related questions

Is log(n!) = Θ(n·log(n))?

I am to show that log(n!) = Θ(n·log(n)). A hint was given that I should show the upper bound with nn and show the lower bound with (n/2)(n/2). This does not seem all that intuitive to me. …

Read More
What's time complexity of this algorithm for finding all combinations?

Combinations Given two integers n and k, return all possible combinations of k numbers out of 1 ... n. For example, If n = 4 and k = 2, a solution is: [ [2, 4], [3, 4], [2, 3], [1, 2], [1, 3], [1, 4], ] Personally I think, time complexity = O(n^k), n and k are input. Thank …

Read More
What is tail recursion?

Whilst starting to learn lisp, I've come across the term tail-recursive. What does it mean exactly?

Read More