Computational complexity of Fibonacci Sequence

by

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?

12 Answers
12

Leave a Comment