Memoization - Time Complexity

With memoization, your time complexity (how the running time grows with input size) drops from $O(2^n)$ to $O(n)$. Why? Because each value from fib(0) to fib(n) is computed exactly once. The first time you call fib(k), you do the work and store it.

Every subsequent call to fib(k) is a constant-time lookup. Since there are n+1 distinct values to compute, and each takes $O(1)$ work after memoization, you get $O(n)$ total time.

That's exponential to linear. A huge difference. For $n=40$: before, over $300$ million calls. After, exactly $41$ calls (one for each value from $0$ to $40$). Let that sink in. fib(50) and even fib(100) now compute in milliseconds.