Analyzing Recursion: The Tree Method

The office hierarchy

Now imagine you are the manager of the post office, and a giant task arrives. Instead of doing it yourself, you divide the task and delegate work to subordinate clerks, who each do the same with their assistants, creating a branching pyramid of effort throughout the office hierarchy. This is a fundamentally different shape than the clerk's repetitive floor tasks from the last lesson — there's no loop to count. Instead, the total work is every delegated piece added back up, however many layers deep the delegation goes.

A recursive function calls itself on smaller inputs, so its total cost is a recurrence — cost at size n expressed in terms of cost at smaller sizes. Draw every call as a node in a tree — the top call is the root, each recursive call is a child — and the total work is every node's cost, added up. Three shapes cover almost everything you'll meet.

Halve and recurse once — O(log n)

The single-chain search. A massive crate of packages arrives, and you need to locate one specific golden package. Instead of doing it yourself, you split the crate in half, figure out which half contains the package, and hand off the entire task to a subordinate — they do the same, passing only half the pile onward each time. At any depth of the delegation, only one person is doing a quick check and the pile size shrinks very fast.

This is binary search: T(n) = T(n/2) + O(1). The tree is a single chain, one child per node: n → n/2 → n/4 → … → 1. That's log n steps, O(1) work at each → O(log n).

Split, recurse twice, merge — O(n log n)

The active pyramid. You have a pile of letters to sort. Instead of doing it yourself, you split the pile in half and hand both halves to two assistants, who split their piles and pass them onward once each. Once the sub-piles are sorted and sent back up, you merge every pair of sorted piles back into one. Every single worker in the hierarchy is active, and if you sum the total effort of physical actions performed across all levels of the pyramid, it is actually proportional to the number of letters in the original crate, and your desk only needs a tiny stack of delegation cards.

This is merge sort: T(n) = 2T(n/2) + O(n). Now each level branches, but also does less work per node — and the two balance out:

Every level totals n, and there are log n levels, so the grand total is n · log n → O(n log n). The per-level total staying flat — not growing, not shrinking — is why the answer is n times log n and not just n or just log n.

Branch twice without shrinking fast — O(2ⁿ)

The exploding staff. Now imagine you have a task, but to solve a task of difficulty n, you must call up two assistants and delegate a task of difficulty n−1 to one and n−2 to the other. Because the difficulty of workers doubles at every single level, and the pyramid of workers grows almost as fast as it shrinks depth-wise, everyone ends up re-scanning and re-solving the same small sub-tasks over and over again.

Naive Fibonacci: T(n) = T(n−1) + T(n−2) + O(1). Here the subproblem barely gets smaller (n−1, not n/2), so the tree stays almost as wide as it is deep. Watch what actually happens computing fib(4) with no memoization — every node is a real function call:

fib(4)
├─ fib(3)
│  ├─ fib(2)
│  │  ├─ fib(1)
│  │  └─ fib(0)
│  └─ fib(1)
└─ fib(2)
   ├─ fib(1)
   └─ fib(0)

fib(2) gets computed twice, fib(1) three times, fib(0) twice — 9 calls total to answer one question with only 5 distinct inputs (0 through 4). That's the whole story of the blowup: the tree doubles nearly every level and is n levels deep → O(2ⁿ)-ish (Θ(φⁿ) precisely, where φ ≈ 1.618 is the golden ratio — the exact constant rarely matters, only that it's exponential). Exponential recursion always comes from re-solving the same subproblems, and you can see it directly in the tree: count the distinct subproblems (here, only 5 — one per value of n) and you've already discovered why memoization (Stage 4) collapses this to O(n): compute each distinct subproblem once, reuse it everywhere it repeats.

The shared bulletin board. As soon as any worker calculates a solution for a task of a given difficulty level, they pin the answer on a shared office bulletin board. Now, as soon as any worker is handed a task, they first walk over and check the board — if the answer is already there, they grab it instantly instead of redoing the work. That single board is the whole idea of memoization and dynamic programming.

Watch the tree grow call by call, in the exact order the real call stack unwinds — every red flash is a subproblem being solved again from scratch:

Notice what separates the three shapes: it was never how many branches a call makes — merge sort and Fibonacci both branch twice per call. It's how fast the input shrinks. Halving gives log n levels; subtracting a constant gives n levels. Depth, not branching factor, decides whether you get a flat n log n or an exploding 2ⁿ.