With memoization, your time complexity (how the running time grows with input size) drops from to . 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 work after memoization, you get total time.
That's exponential to linear. A huge difference. For : before, over a billion calls. After, exactly calls (one Each value from to ). Let that sink in. fib(50) and even fib(100) now compute in milliseconds.