A strong answer
The naive version, fib(n) = fib(n − 1) + fib(n − 2) with base cases 0 and 1, recomputes the same values over and over. Its recursion tree branches twice at every call, and because the input shrinks by only 1 or 2 per level, the tree is about n levels deep. The number of calls is 2·fib(n + 1) − 1, which grows by a factor of about 1.618 per step: fib(40) makes about 331 million calls to compute an answer that depends on only 41 distinct values. Its stack depth is only O(n), but its time is exponential.
Three fixes, each better than the last for this problem:
- Memoization. Cache each result the first time it is computed. Each n from 0 to the target is computed once: O(n) time, O(n) space for the cache and O(n) stack depth.
- Bottom-up table. Fill an array from 0 upward,
f[i] = f[i − 1] + f[i − 2]. O(n) time, no recursion. - Two variables. Each step needs only the previous two values, so keep those two: O(n) time, O(1) space.
There is also an O(log n) method, using matrix exponentiation or the doubling identities fib(2k) = fib(k)·(2·fib(k + 1) − fib(k)) and fib(2k + 1) = fib(k)² + fib(k + 1)², which halve n at each step like fast power. With 64-bit unsigned integers, fib(93) is the largest that fits.
What the interviewer is listening for
- Overlapping subproblems as the cause, shown with the recursion tree.
- A correct count or growth rate for the naive calls.
- The progression from memoization to O(1) space, with each version's time and space.
Common mistakes
- Calling the naive version O(2ⁿ) without noticing it is about 1.618ⁿ (acceptable as an upper bound, but say which you mean).
- Confusing stack depth with the number of calls.
- Forgetting overflow for large n.