Why is the complexity of computing the Fibonacci s

Question

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 1

Look at it like this. Assume the complexity of calculating F(k), the kth Fibonacci number, by recursion is at most 2^k for k <= n. This is our induction hypothesis. Then the complexity of calculating F(n + 1) by recursion is

F(n + 1) = F(n) + F(n - 1)

which has complexity 2^n + 2^(n - 1). Note that

2^n + 2^(n - 1) = 2 * 2^n / 2 + 2^n / 2 = 3 * 2^n / 2 <= 2 * 2^n = 2^(n + 1).

We have shown by induction that the claim that calculating F(k) by recursion is at most 2^k is correct.

Answer 2

t(n)=t(n-1)+t(n-2) which can be solved through tree method:

                                  t(n-1)  +  t(n-2)        2^1=2
                                   |         |  
                            t(n-2)+t(n-3)  t(n-3)+t(n-4)   2^2=4  
                                .               .          2^3=8
                                .               .           .
                                .               .           .

similarly for the last level . . 2^n
it will make total time complexity=>2+4+8+.....2^n after solving the above gp we will get time complexity as O(2^n)

Answer 3

The complexity of recursive Fibonacci series is 2^n:
This will be the Recurrence Relations for recursive Fibonacci

 T(n)=T(n-1)+T(n-2)                  No  of elements  2

Now on solving this relation using substitution method (substituting value of T(n-1) and T(n-2))

T(n)=T(n-2)+2*T(n-3)+T(n-4)          No  of elements  4=2^2

Again substituting values of above term we will get

T(n)=T(n-3)+3*T(n-4)+3*T(n-5)+T(n-6)  No  of elements  8=2^3

After solving it completely, we get

T(n)={T(n-k)+---------+---------}----------------------------->2^k  eq(3) 

This implies that maximum no of recursive calls at any level will be at most 2^n.
And for all the recursive calls in equation 3 is ϴ(1) so time complexity will be 2^n* ϴ(1)=2^n

Answer 4

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)

Answer 5

The recursion tree for fib(n) would be something like :

                              n       
                           /     \
                          n-1    n-2      --------- maximum 2^1 additions
                         /  \    /   \
                       n-2   n-3 n-3 n-4  -------- maximum 2^2 additions
                      /   \           
                     n-3 n-4              -------- maximum 2^3 additions         
                                                ........
                                          -------- maximum 2^(n-1) additions  

1. Using n-1 in 2^(n-1) since for fib(5) we will eventually go down to fib(1)
2. Number of internal nodes = Number of leaves - 1 = 2^(n-1) - 1
3. Number of additions = Number of internal nodes + Number of leaves = (2^1 + 2^2 + 2^3 + ...) + 2^(n-1)
4. We can replace the number of internal nodes to 2^(n-1) - 1 because it will always be less than this value : = 2^(n-1) - 1 + 2^(n-1) ~ 2^n

Answer 6

The O(2^n) complexity of Fibonacci number calculation only applies to the recursion approach. With a few extra space, you can achieve a much better performance with O(n).

public static int fibonacci(int n) throws Exception {

  if (n < 0)
    throws new Exception("Can't be a negative integer")

  if (n <= 1)
    return n;

  int s = 0, s1 = 0, s2 = 1;
  for(int i= 2; i<=n; i++) {
    s = s1 + s2;
    s1 = s2;
    s2 = s;            
  }
  return s;
}