Using a recursion tree, why does T(n)=4T(n/4)+O(n) come out as O(n log n) and not exponential?

## The scenario Satellite imagery is usually served as a pyramid: the full-resolution tile at the bottom, and above it progressively coarser summaries, each pixel of a coarse level aggregating a block of the level below. A natural way to build one is quad-tree recursion — split the tile into four quadrants, build each quadrant's summary recursively, then walk the four results once to combine them into this node's summary. If the tile holds n pixels, each quadrant holds n/4, and the combining pass is proportional to the number of pixels involved. The recurrence writes itself: `T(n) = 4T(n/4) + O(n)` A first reaction is often "four-way branching, that must blow up" — 4 calls, then 16, then 64. It does not, and the recursion tree shows why in three numbers. ## Drawing the tree, in three steps **Step 1 — what does one level hold?** The root is one node on n pixels. It has 4 children on n/4 each. Those have 4 children each on n/16. In general, **level i has 4^i nodes, each on an input of size n/4^i**. **Step 2 — what does one level cost?** Label each node with its own non-recursive work only — here, c times its input size, because the combine pass is linear in what it touches. Level i therefore costs > 4^i nodes × c·(n/4^i) per node = c·n The two exponentials cancel. Node count grows by 4 per level; per-node work shrinks by 4 per level. **Every level costs about n.** That cancellation is the whole answer, and it happens precisely because the branching factor equals the shrink factor. **Step 3 — how many levels?** Sizes go n, n/4, n/16, … and hit the base case when n/4^k is constant, so k ≈ log₄ n. Multiply: total = c·n·log₄ n = **O(n log n)**. Check the bottom row as a sanity test. There are 4^(log₄ n) = n leaves, each doing constant work, so the leaves contribute Θ(n) in total — exactly one level's worth. Nothing at the bottom dominates, which is consistent with the picture of equal levels. If your leaf count ever comes out larger than your per-level work, you have made an arithmetic error somewhere. ## Where branching really does explode The fan-out alone never decides. What decides is the *race* between the node count and the shrinking per-node work. Compare three trees, all with four children per node: | Recurrence | Level i cost | Total | |---|---|---| | `T(n)=4T(n/4)+O(n)` | c·n, flat | Θ(n log n) | | `T(n)=4T(n/4)+O(1)` | 4^i, growing | Θ(n), leaf-dominated | | `T(n)=4T(n/2)+O(n)` | c·n·2^i, growing fast | Θ(n²) | The last row is the interesting one. Four calls on *half*-sized inputs means the node count quadruples while the per-node work only halves, so level costs double as you descend: c·n, 2c·n, 4c·n, … over log₂ n levels. That is an increasing geometric series dominated by its last term, and the bottom level holds 4^(log₂ n) = n² leaves. The result is Θ(n²). Same fan-out, completely different answer — because the subproblems shrink too slowly. Truly exponential behaviour needs subproblems that barely shrink at all: branching where the child is size n−1 rather than n/b. Then the depth is n rather than log n and the node count is a constant raised to the power n. Quarter-sized children can never produce that, no matter how wide the fan-out, because the total input size at each level is conserved rather than multiplied. ## Two details interviewers probe **The base of the log.** The depth here is log₄ n, not log₂ n. Since log₄ n = (log₂ n)/2, the tree is genuinely half as deep as a binary-splitting tree — real, measurable, and invisible to the O( ) label, which absorbs constant factors. If someone claims the four-way version is asymptotically faster, that is the mistake to name. If someone claims it is identical in wall-clock terms, that is the opposite mistake: fewer levels can mean fewer passes over memory, which is exactly why real aggregation code often fans out wider than two. **Non-uniform levels.** The clean "multiply per-level work by number of levels" shortcut is only valid when the levels cost the same. When the level costs form a geometric series, sum the series instead: a decreasing one is dominated by the root, an increasing one by the leaves. Always ask which of the three regimes you are in before multiplying. ## How to present it Say the three numbers in order — nodes per level, work per node, number of levels — and then multiply. That derivation transfers to any recurrence you have never seen, and it is the reason interviewers ask for the tree rather than the answer: the answer for this shape is memorable, and the method is what they are actually testing.