Computational complexity of Fibonacci Sequence
- by Juliet
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 Fib(int n)
{
if (n <= 1)
return 1;
else
return Fib(n - 1) + Fib(n - 2);
}
What is the computational complexity of the Fibonnaci sequence and how is it calculated?