The Big O table was memorised before the first onsite. Binary search logarithmic, merge sort linearithmic, hash insert constant amortised. All recitable. Then a senior engineer wrote a recursive function on the whiteboard, asked for an analysis, and almost a minute went by trying to match what was on the board to something on the cached table. The function was a naive recursive Fibonacci, seen before, implemented before. The freeze still happened, because nothing about the table told anyone how to count the recursive calls.
- The table is the answer, not the method. Memorising it never builds the ability to derive complexity from code you haven't seen.
- The thing the table hides is the counting. How many times the dominant operation runs as a function of input size.
- Once four or five derivations have been traced by hand, the shape generalises. Unfamiliar code stops feeling opaque.
- Space complexity has the same derivation shape, plus the call stack that's easy to forget.
- The drill that actually builds the skill is deriving complexity on problems whose answer you don't already know.
Where the approach was breaking
The Fibonacci moment exposed the gap. The function had been seen. The function had been implemented. What hadn't happened was counting what the recursion actually does.
def fib(n):
if n < 2:
return n
return fib(n - 1) + fib(n - 2)
The interviewer was patient. "How many calls does fib(5) make?" The whiteboard got a tree. fib(5) calls fib(4) and fib(3). fib(4) calls fib(3) and fib(2). fib(3) shows up twice. fib(2) shows up three times. The tree grew faster than the page it was being drawn on. The answer wasn't in cached memory because no one had asked for the count before. The answer is O(2ⁿ), roughly, and the reason is that each call branches into two and the depth is about n.
Big O had been treated as a label to attach after solving. The interview was treating it as a derivation to perform on unfamiliar code. Those are different skills, and the wrong one had been practiced.
What started working differently
The fix wasn't reading more articles. It was changing the drill. The new prompt was "given this code you haven't seen before, what's the complexity, and how would you justify it" instead of "what's the complexity of merge sort." Once the prompt changed, the way unfamiliar code reads changed with it.
Here's the shape that worked, side by side with the old habit:
| Then | Now |
|---|
| Match the code to a memorised complexity. | Identify the dominant operation, the one that runs most. |
| Look up the answer when the match wasn't obvious. | Count how many times that operation runs, as a function of n. |
| Move on once a label was attached. | Sum the work across levels (loops, recursion depth, branching factor). |
| Forget about space until reminded. | Track space the same way: auxiliary memory plus the call stack. |
The change is a habit, not a piece of knowledge. The Big O table doesn't get more correct over time. The way unfamiliar code gets read does.
What that looked like on the next problem
A few weeks after the Fibonacci interview, the same function came back out for re-derivation from scratch. No looking up the answer. Just the dominant operation and counting.
The dominant operation in fib(n) is the recursive call. fib(n) calls fib(n-1) and fib(n-2). Treat both as roughly fib(n-1) for the upper bound. So the call count T(n) ≈ 2 × T(n-1). That recurrence solves to T(n) = 2ⁿ. The depth of the tree is about n. The branching factor is 2. Total work is roughly the number of nodes in a binary tree of depth n, which is 2ⁿ.
That's why naive Fibonacci is unusably slow even at moderate n. fib(40) makes more than a billion calls.
Adding memoisation changes the shape entirely:
def fib(n, memo={}):
if n in memo:
return memo[n]
if n < 2:
return n
memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
return memo[n]
Now each subproblem fib(k) for k from 0 to n is computed exactly once. There are n distinct subproblems. Each one does constant work after its two subcalls return. Total: O(n) time, O(n) space from the memo plus the call stack.
The complexity went from O(2ⁿ) to O(n) because the structure of the work changed, and the derivation made that visible in a way the table never did. (For the longer walkthrough of how memoisation becomes the gateway to dynamic programming, the DP interview blog covers the recurrence-to-table-to-bottom-up progression.)
Why this works (the science behind it)
The learning science term for the swapped drill is elaborative interrogation. Asking yourself why each operation contributes the work it does, rather than accepting the labelled answer at face value. The literature on it is consistent: forcing yourself to construct the reason produces a more durable, more transferable understanding than reading the reason already constructed.
The other piece is near transfer versus far transfer. The old drill was near transfer practice (the same complexity question on the same code already memorised). The interview was a far transfer test (different code, same skill). Near transfer practice doesn't reliably move far transfer scores. Once that lands, the right drill picks itself: derive complexity on code you haven't seen.
What to tell someone in the same spot
Three things, in the order they mattered.
- Stop quizzing yourself on named algorithms. "What's the complexity of merge sort" trains memory, not derivation. Quiz yourself on an unfamiliar function instead, and force yourself to count the dominant operation explicitly. If you have to count it out loud, that's the right intensity.
- Trace at least one recursive call tree by hand per week. The first few feel slow. The fifth or sixth is where the shape generalises. Branching factor times depth gives nodes, nodes times work-per-node gives total work. The arithmetic is the same on every problem.
- Track space the same way you track time. Auxiliary memory plus call-stack frames. Most engineers in interviews get time right and space wrong, and the difference is purely habit.
Before this shift, a solution would read as that looks fast and the analysis would stop there. After, the same solution reads as O(n log n) because the divide step and the merge step can be pointed at independently. Adding a hash map to a nested loop visibly drops the complexity from quadratic to linear, with the derivation right there in the code. Unfamiliar code becomes analysable because the analysis is something you do, not something you recall.
Originally posted on my own blog, with the amortised analysis derivation for hash-map resize and the space-complexity traps skipped over in this retrospective.
What's a piece of complexity analysis that finally clicked for you only after deriving it by hand, where the textbook label had never really stuck?