Assuming Every Halving Recurrence Is O(n log n)

A recurrence that halves its input and does linear work outside the calls is O(n log n) only when it makes exactly two calls. This card shows what changes when it makes four: T(n) = 4T(n/2) + n is O(n²), solved here both by a recursion tree and by the master theorem.

The symptom is a design costed at O(n log n) that runs quadratically: doubling the input makes it four times slower, not a little over twice. The trigger is matching by shape. "It halves, and it does a linear pass" sounds like merge sort, so the answer gets copied from merge sort, and the number of calls is never looked at.

Draw both trees at n = 8 and total their levels. Both start with 8 work at the root, and both have four levels. The difference is how many nodes each level holds: two children per node double the count, four children quadruple it, while the size per node halves in both.

With two calls every level costs n. With four, each level costs twice the one above it, so the bottom level alone, 64 leaves of 1 work each, is more than half the total. A program that expanded every call printed these totals, and at n = 16 it printed 80 for two calls and 496 for four.

The master theorem says the same thing in one line. For 4T(n/2) + n, a is 4 and b is 2, so n^(log₂ 4) is n², which outgrows the n of work per call: case 1, and the cost is O(n²), the leaf count. For 2T(n/2) + n, n^(log₂ 2) is n, the same as the work per call: case 2, and O(n log n).

The cost is a design that is no better than the simple method it was meant to replace. Multiplying two n × n matrices by splitting each into four blocks of half the size takes eight half-size block products and some additions of blocks, each O(n²): T(n) = 8T(n/2) + O(n²). Since n^(log₂ 8) is n³, that is O(n³), exactly what the three nested loops of the ordinary method cost. The split alone buys nothing, because the number of calls grew as fast as their size shrank.

Before writing O(n log n) for a recurrence, work out n^(log_b a) and compare it with f(n). Linear work gives O(n log n) only when that comparison is a tie, which for halving means exactly two calls. A divide-and-conquer design gets faster by making fewer calls, not by making them smaller.