Computational complexity of Fibonacci Sequence

Question

I understand Big-O notation, but I don't know how to calculate it for many functions. In particular, I've been trying to figure out the computational complexity of the naive version of the Fibonacci sequence:

int Fibonacci(int n)
{
    if (n <= 1)
        return n;
    else
        return Fibonacci(n - 1) + Fibonacci(n - 2);
}

What is the computational complexity of the Fibonacci sequence and how is it calculated?

Answer 1

This performs way better:

unsigned int Fib(unsigned int n)
{
    // first Fibonaci number is Fib(0)
    // second one is Fib(1) and so on

    // unsigned int m;  // m + current_n = original_n
    unsigned int a = 1; // Fib(m)
    unsigned int b = 0; // Fib(m-1)
    unsigned int c = 0; // Fib(m-2)

    while (n--)
    {
        c = b;
        b = a;
        a = b+c;
    }

    return a;
}

Answer 2

Recursive algorithm's time complexity can be better estimated by drawing recursion tree, In this case the recurrence relation for drawing recursion tree would be T(n)=T(n-1)+T(n-2)+O(1) note that each step takes O(1) meaning constant time,since it does only one comparison to check value of n in if block.Recursion tree would look like

          n
   (n-1)      (n-2)
(n-2)(n-3) (n-3)(n-4) ...so on

Here lets say each level of above tree is denoted by i hence,

i
0                        n
1            (n-1)                 (n-2)
2        (n-2)    (n-3)      (n-3)     (n-4)
3   (n-3)(n-4) (n-4)(n-5) (n-4)(n-5) (n-5)(n-6)

lets say at particular value of i, the tree ends, that case would be when n-i=1, hence i=n-1, meaning that the height of the tree is n-1. Now lets see how much work is done for each of n layers in tree.Note that each step takes O(1) time as stated in recurrence relation.

2^0=1                        n
2^1=2            (n-1)                 (n-2)
2^2=4        (n-2)    (n-3)      (n-3)     (n-4)
2^3=8   (n-3)(n-4) (n-4)(n-5) (n-4)(n-5) (n-5)(n-6)    ..so on
2^i for ith level

since i=n-1 is height of the tree work done at each level will be

i work
1 2^1
2 2^2
3 2^3..so on

Hence total work done will sum of work done at each level, hence it will be 2^0+2^1+2^2+2^3...+2^(n-1) since i=n-1. By geometric series this sum is 2^n, Hence total time complexity here is O(2^n)

Answer 3

You model the time function to calculate Fib(n) as sum of time to calculate Fib(n-1) plus the time to calculate Fib(n-2) plus the time to add them together (O(1)).

T(n<=1) = O(1)

T(n) = T(n-1) + T(n-2) + O(1)

You solve this recurrence relation (using generating functions, for instance) and you'll end up with the answer.

Alternatively, you can draw the recursion tree, which will have depth n and intuitively figure out that this function is asymptotically O(2n). You can then prove your conjecture by induction.

Base: n = 1 is obvious

Assume T(n-1) = O(2n-1), therefore

T(n) = T(n-1) + T(n-2) + O(1) which is equal to

T(n) = O(2n-1) + O(2n-2) + O(1) = O(2n)

However, as noted in a comment, this is not the tight bound. An interesting fact about this function is that the T(n) is asymptotically the same as the value of Fib(n) since both are defined as

f(n) = f(n-1) + f(n-2).

The leaves of the recursion tree will always return 1. The value of Fib(n) is sum of all values returned by the leaves in the recursion tree which is equal to the count of leaves. Since each leaf will take O(1) to compute, T(n) is equal to Fib(n) x O(1). Consequently, the tight bound for this function is the Fibonacci sequence itself (~θ(1.6n)). You can find out this tight bound by using generating functions as I'd mentioned above.

Answer 4

It is bounded on the lower end by 2^(n/2) and on the upper end by 2^n (as noted in other comments). And an interesting fact of that recursive implementation is that it has a tight asymptotic bound of Fib(n) itself. These facts can be summarized:

T(n) = Ω(2^(n/2))  (lower bound)
T(n) = O(2^n)   (upper bound)
T(n) = Θ(Fib(n)) (tight bound)

The tight bound can be reduced further using its closed form if you like.

Answer 5

There's a very nice discussion of this specific problem over at MIT. On page 5, they make the point that, if you assume that an addition takes one computational unit, the time required to compute Fib(N) is very closely related to the result of Fib(N).

As a result, you can skip directly to the very close approximation of the Fibonacci series:

Fib(N) = (1/sqrt(5)) * 1.618^(N+1) (approximately)

and say, therefore, that the worst case performance of the naive algorithm is

O((1/sqrt(5)) * 1.618^(N+1)) = O(1.618^(N+1))

PS: There is a discussion of the closed form expression of the Nth Fibonacci number over at Wikipedia if you'd like more information.

Answer 6

http://www.ics.uci.edu/~eppstein/161/960109.html

time(n) = 3F(n) - 2