# Is the time complexity of the Fibonacci sequence O(fib(n))?

I started watching SICP lectures and am totally new to computer science. SICP. LEC 1B: Procedures and Processes; Substitution Model

I don't know why the time complexity of the Fibonacci sequence is O(Fib(n)). So, I googled about it,

he says

There's a thing that grows exactly at Fibonacci numbers. It's a horrible thing. You wouldn't want to do it. The reason why the time has to grow that way is because we're presuming in the model-- the substitution model that I gave you, which I'm not doing formally here, I sort of now spit it out in a simple way-- but presuming that everything is done sequentially. That every one of these nodes in this tree has to be examined. And so since the number of nodes in this tree grows exponentially because I add a proportion of the existing nodes to the nodes I already have to add one, then I know I've got an exponential explosion here.

Can anybody please explain what he's saying?

• "time complexity of the Fibonacci sequence" -- by itself, a sequence doesn't have a time complexity. Do you mean the time complexity of computing the $n$-th element of the Fibonacci sequence is $O(Fib(n))$? Because even the straightforward method of repeatedly adding the last 2 terms together is exponentially faster than that, and using exponentiation by squaring to evaluate Binet's formula is exponentially faster than that. – j_random_hacker Feb 23 at 10:14

$$\DeclareMathOperator{\fib}{fib}$$If you choose to calculate $$\fib(n)$$ by using the naive recursion formula, then you need $$\Theta (\fib(n))$$ additions, and since the numbers involved grow to $$c\cdot n$$ bits for a not very large constant $$c$$, it will take $$\Theta(n \cdot \fib(n))$$ operations. (I may be wrong here because most of the numbers involved may be much smaller than $$c \cdot n$$ bits).
If you are reasonably clever and calculate $$\fib(0), \fib(1), \fib(2), \dots, \fib(n),$$ then you have $$n$$ additions of $$c \cdot n$$ bit numbers, which takes $$\Theta(n^2))$$ operations.
You can use matrix exponentiation to calculate $$\fib(n)$$ faster for large $$n$$, I'd estimate something like $$M(n)$$ where $$M(n)$$ is the time for an $$n$$-bit multiplication.
Most important is that for maybe $$n = 100$$ or $$n = 200$$, your computer has not a chance to calculate $$\fib(n)$$ using the naive recursive algorithm within your lifetime, while the simple method of calculating consecutive values will find the same result within microseconds on a newish smartphone.
• There's even a closed form formula: $\left( \phi^n - (-\phi)^n \right) / \sqrt{5}$, where $\phi = (1 + \sqrt{5}) / 2$ is the golden ratio. – Pål GD Feb 23 at 11:27
• @PålGD As suggested by gnasher729, matrix exponentiation (which is really just a recurrence $(F_n,F_{n+1})\mapsto(F_{2n},F_{2n+1})$ if you don’t want to speak of matrices) is faster that computing $\phi^n$, as the latter needs to maintain working precision of $O(n)$ bits during the whole computation. That is, computing $F_n$ using matrix exponentiation takes $O(M(n))$ bit operations, whereas using $\phi^n$ it takes $O(M(n)\log n)$ operations. The algorithm using matrix exponentiation is also easier to implement, as it works purely with integers. – Emil Jeřábek Feb 23 at 12:15