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

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

Ho开发者_StackOverflow中文版w come it is O(2^n)?

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)

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

You are correct that the depth of the tree is O(n), but you are not doing O(n) work at each level. At each level, you do O(1) work per recursive call, but each recursive call then contributes two new recursive calls, one at the level below it and one at the level two below it. This means that as you get further and further down the recursion tree, the number of calls per level grows exponentially.

Interestingly, you can actually establish the exact number of calls necessary to compute F(n) as 2F(n + 1) - 1, where F(n) is the nth Fibonacci number. We can prove this inductively. As a base case, to compute F(0) or F(1), we need to make exactly one call to the function, which terminates without making any new calls. Let's say that L(n) is the number of calls necessary to compute F(n). Then we have that

L(0) = 1 = 2*1 - 1 = 2F(1) - 1 = 2F(0 + 1) - 1

L(1) = 1 = 2*1 - 1 = 2F(2) - 1 = 2F(1 + 1) - 1

Now, for the inductive step, assume that for all n' < n, with n ≥ 2, that L(n') = 2F(n + 1) - 1. Then to compute F(n), we need to make 1 call to the initial function that computes F(n), which in turn fires off calls to F(n-2) and F(n-1). By the inductive hypothesis we know that F(n-1) and F(n-2) can be computed in L(n-1) and L(n-2) calls. Thus the total runtime is

1 + L(n - 1) + L(n - 2)

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

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

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

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

= 2F(n + 1) - 1

Which completes the induction.

At this point, you can use Binet's formula to show that

L(n) = 2(1/√5)(((1 + √5) / 2)ⁿ - ((1 - √5) / 2)ⁿ) - 1

And thus L(n) = O(((1 + √5) / 2)ⁿ). If we use the convention that

φ = (1 + √5) / 2 ≈ 1.6

We have that

L(n) = Θ(φⁿ)

And since φ < 2, this is o(2ⁿ) (using little-o notation).

Interestingly, I've chosen the name L(n) for this series because this series is called the Leonardo numbers. In addition to its use here, it arises in the analysis of the smoothsort algorithm.

Hope this helps!

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.

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)

The complexity of Fibonacci series is O(F(k)), where F(k) is the kth Fibonacci number. This can be proved by induction. It is trivial for based case. And assume for all k<=n, the complexity of computing F(k) is c*F(k) + o(F(k)), then for k = n+1, the complexity of computing F(n+1) is c*F(n) + o(F(n)) + c*F(n-1) + o(F(n-1)) = c*(F(n) + F(n-1)) + o(F(n)) + o(F(n-1)) = O(F(n+1)).

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

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;
}

I cannot resist the temptation of connecting a linear time iterative algorithm for Fib to the exponential time recursive one: if one reads Jon Bentley's wonderful little book on "Writing Efficient Algorithms" I believe it is a simple case of "caching": whenever Fib(k) is calculated, store it in array FibCached[k]. Whenever Fib(j) is called, first check if it is cached in FibCached[j]; if yes, return the value; if not use recursion. (Look at the tree of calls now ...)