Why isn't every divide-and-conquer algorithm O(n log n)?

## The three knobs Write the cost of a divide-and-conquer algorithm as a recurrence: `T(n) = a * T(n/b) + f(n)` - **`a`** — how many recursive calls each level makes (the branching factor). - **`b`** — how much smaller each subproblem is (the shrink factor). - **`f(n)`** — the work done *outside* the recursive calls: splitting plus combining. Every one of these moves the total independently, and `n log n` is what you get from one particular combination. Solving such recurrences formally has its own machinery and is a complexity-analysis topic in its own right; what follows is the intuition an interviewer wants to hear. ## Where each factor comes from The **`log n`** is the *depth*. If every call shrinks the input by a constant factor `b`, then after `k` levels the input has size `n / b^k`, and the recursion bottoms out when that reaches the base case — after about `log_b n` levels. Constant-factor shrinking is the only thing that produces the logarithm. Shrinking by a constant *amount* (`n` down to `n-1`) gives `n` levels instead. The **`n`** is the *per-level work*. In the classic shape, the top call does `Θ(n)` work, the two half-size calls do `Θ(n/2)` each — `Θ(n)` together — the four quarter-size calls do `Θ(n)` together, and so on. Every level costs the same, and there are `log n` of them, so the total is `Θ(n log n)`. That coincidence — equal work at every level — is exactly what makes the shape memorable and exactly why people over-generalise it. ## Four recurrences, four different answers | recursive calls | subproblem size | work outside recursion | total | |---|---|---|---| | 1 | n/2 | Θ(1) | Θ(log n) | | 2 | n/2 | Θ(1) | Θ(n) | | 2 | n/2 | Θ(n) | Θ(n log n) | | 2 | n/2 | Θ(n²) | Θ(n²) | | 1 | n−1 | Θ(n) | Θ(n²) | Read the rows as three regimes: **The leaves dominate.** With two half-size calls and constant combine work, the recursion tree has about `n` leaves, each costing `Θ(1)`, and every level costs *twice* the level above it. The bottom level alone is `Θ(n)` and it swamps everything else, so the total is `Θ(n)` — no logarithm in sight, even though the input is being halved. **Every level ties.** Two half-size calls with linear combine work is the balanced case: `Θ(n)` per level, `log n` levels, `Θ(n log n)` total. **The root dominates.** Two half-size calls with a quadratic combine costs `Θ(n²)` at the top, `2 * Θ(n²/4) = Θ(n²/2)` at the next level, then `Θ(n²/4)`, and so on — a geometric series that sums to `Θ(n²)`. The outermost call is essentially the whole bill, and no amount of clever recursion beneath it helps. ## Decrease-and-conquer: the one-branch case Exponentiation by repeated squaring is the cleanest counterexample, because it looks like divide and conquer and behaves completely differently. To compute `x^n`, compute `x^(n/2)` **once** and square it, adjusting by one extra multiplication when `n` is odd. The exponent halves every level, so the depth is about `log n`, and each level does a constant number of multiplications — total `O(log n)`. If it had needed *both* halves computed separately, the same halving would have produced `Θ(n)` work instead. The branching factor, not the halving, is what separates the two. The reverse trap is just as common: a "split" that separates one element from the remaining `n-1` while doing linear work per call gives `n` levels of `Θ(n)` work, so `Θ(n²)`. The word *divide* was used honestly; the shrink factor was not a factor at all. ## The interview move When you are asked for the cost of a divide-and-conquer design, do not reach for a remembered answer. Say how many recursive calls it makes, how much smaller each call's input is, and how much work happens outside those calls — then reason about whether the levels grow, shrink or tie. Three sentences, and they are correct for every recurrence in the family rather than for one famous member of it.