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?