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?
$\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.