Time Complexity - Exponential Growth

Your naive Fibonacci runs in $O(2^n)$ time and uses $O(n)$ space. (Well, honestly not exactly this. But let's go with that for now) Why? Each call makes two more calls, creating a binary tree of depth $n$.

That's roughly $2^n$ total calls. Try it: $fib(10)$ makes hundreds of calls, $fib(20)$ makes thousands, $fib(40)$ makes hundreds of millions. Exponential growth is brutal. Adding just $1$ to $n$ almost doubles the work.

This is why $fib(5)$ finishes quickly but $fib(50)$ would take years. How do we fix this? Before you read the next unit, try to answer: what if you could remember answers you've already computed? How would that change things?