Divide and conquer

Sixteen numbered cards lie face down on a table. Split them into two piles of eight, sort each pile, then merge the two sorted piles by repeatedly taking the smaller of the two top cards. The merge never needs more than fifteen comparisons: each comparison removes one card from a pile, and once one pile is empty the remaining cards are placed without comparing, so fifteen removals settle sixteen cards. Sorting eight cards the same way needs 17, and 17 + 17 + 15 is 49 [S:5:880]. Doubling the pile therefore takes almost three times the work rather than twice, which is the first indication that the shape of the work has changed.

The pattern is called divide and conquer, and it has three steps: divide the problem into smaller instances of the same kind, solve each instance, and combine the answers into one [S:1:49]. The cost of the pattern is written as a recurrence, an equation that gives the cost at size n in terms of the cost at smaller sizes. A recurrence is not yet an answer, so a picture called a recursion tree turns it into a sum you can evaluate. The sum shows which term dominates, meaning which term grows fastest and sets the total. !Sorting eight cards, drawn as the recurrence. The root pays 7 comparisons to merge, its two children 3 each, its four grandchildren 1 each, and the eight leaves nothing: 7 + 6 + 4 + 0 = 17. Every level costs close to n, and halving stops after three levels, which is where the logarithm comes from. Status: schematic.

For the card procedure the split is even and the combine step is a merge, so sorting n cards costs two sorts of n/2 cards plus at most n − 1 comparisons to merge, which produces the recurrence below. The base case is the smallest instance, the one the rule answers without calling itself: a single card, which is already sorted and needs no comparisons. When n is odd the halves differ by one, and the recurrence is applied to the two whole piles, the larger one carrying the extra card. !Three recurrences, three shapes of level sum. When the root dominates, the top level is nearly the whole cost; when every level is equal, the number of levels, a logarithm, multiplies it; when the leaves dominate, the leaf count sets the cost. The middle case is merge sort. Status: schematic.

Worked example. Compute the recurrence by hand at the sizes a table can hold.

The row for eight cards is the verification: two sorts of four cards cost 5 each, the merge costs 7, and the total is 17. The row for sixteen repeats the operation, since 17 + 17 + 15 is 49, which agrees with the opening claim. It also agrees with the closed form, a formula that produces the total directly without a recurrence: n log₂ n − n + 1 gives sixteen times four, which is 64, and 64 − 16 + 1 is 49. The row for thirty-two produces 49 + 49 + 31 = 129.

$$C(n)=2C(n/2)+n-1$$

Sorting n cards costs twice the cost of sorting half of them, plus the merge.

The recursion tree explains where the logarithm originates. Draw the root at the top, one node for the whole job of eight cards; its two children are the jobs of four cards each, and their four children are the jobs of two cards each. The bottom row of nodes holds the leaves, the jobs with no further calls, and here each leaf is a single card. The root costs 7 comparisons, because that is the merge of eight cards; each child costs 3, because that is the merge of four; each grandchild costs 1. The levels therefore sum to 7, 6, 4 and 0, and the total is 17, which is the value in the table and in the closed form.

The three shapes a level sum can take each correspond to a different outcome. A decreasing sum means each level costs less than the one above, so the root dominates and the cost equals the root's cost; that happens when a procedure scans the whole input and then recurses on half of it. An increasing sum means each level costs more, so the leaves dominate and the cost equals the number of leaves. A procedure that makes four recursive calls on half-sized inputs has four times as many nodes at each level, and its cost grows like n², because n raised to the logarithm base two of four is n².

An equal sum, which is the situation for the card procedure, produces the logarithm, because every level costs the same and the number of levels is what varies [S:1:51]. A geometric sum of levels has only these three shapes, since each level is a fixed multiple of the one above it.

The classification is not a curiosity, because each shape tells you where to concentrate the optimisation effort, whether on the combining work at the root or on the number of recursive calls at the leaves. When the root dominates, the combining work at the top of the tree is the bottleneck, and a faster merge is the only change that matters. When the leaves dominate, the number of recursive calls is the bottleneck, and reducing the branching factor, the number of calls each call makes, is the only change that matters.

In a data pipeline this distinction decides whether doubling the input merely doubles the run time or makes the job impossible, which is the practical form of the chapter's opening question. The recurrence is the instrument that tells you which case you are in before you run the program, and the table above is the smallest possible check that the instrument reads correctly.

At a thousand cards the cost is approximately ten thousand comparisons, against half a million for the all-pairs procedure of the first section. The logarithm is small, which is why the improvement is substantial: doubling the pile adds one level rather than doubling every level. This is the same lesson as the growth ladder, applied to a procedure that constructs its own smaller problems instead of looping over the input.

The prediction depends on the split being even, and that assumption is doing real work. If the split is as uneven as possible, one part has n − 1 items and the other has one. The tree becomes a path of n levels, and every level still pays about n comparisons to merge, so the total is the sum of the numbers from one to n, which is n(n + 1)/2 and grows like n² [S:1:52].

The analysis also brushes aside floors and ceilings and the memory required to hold the two halves while they merge. The floor of a number is the largest whole number at or below it, the ceiling is the smallest whole number at or above it, and the closed form quietly assumes that n halves exactly. The number it produces is therefore a shape rather than a stopwatch reading.

The formal statement. A divide-and-conquer recurrence has the form $T(n)=aT(n/b)+f(n)$ for $n>n_0$. Here $a\ge 1$ counts the subproblems, $b>1$ is the shrink factor, and $f(n)$ is the cost of dividing and combining [S:5:895]. The master theorem gives three cases. When $f(n)$ is smaller than $n^{{\log }_{b}a}$ by a polynomial factor, $T(n)=\Theta (n^{{\log }_{b}a})$. When the two are within a logarithmic factor, $T(n)$ gains one logarithm. When $f(n)$ is larger by a polynomial factor and the regularity condition holds, $T(n)=\Theta (f(n))$ [S:5:895]. The general statement is Akra–Bazzi, which allows several subproblem sizes and absorbs floors and ceilings through perturbation functions [S:5:893].

The derivation. A recursion tree has $a^i$ nodes at depth $i$, each paying $f(n/b^i)$, so the total is the sum of $a^{i}f(n/b^i)$ over the levels [S:1:58]. Put $f(n)=cn$. The sum becomes $cn$ times the sum of $(a/b{)}^i$. The ratio $a/b$ decides everything. Below one the series converges and the root dominates. Equal to one, every level costs $cn$ and there are ${\log }_{b}n$ levels. Above one the last level dominates and the count is the number of leaves, which is $a^{{\log }_{b}n}=n^{{\log }_{b}a}$. The master theorem is this comparison written out in cases.

The edge case. The exact merge-sort recurrence is $T(n)=T(\lceil n/2\rceil )+T(\lfloor n/2\rfloor )+n-1$ [S:5:893]. The core wrote $2T(n/2)+n-1$, which is defined only when $n$ is even. Akra–Bazzi says that perturbations of size $O(n/{\log }^{2}n)$ do not change the asymptotic answer, so the simplification is licensed [S:5:893]. The license is a theorem, not a convention.

A second edge. Boundary conditions can matter when the recurrence is homogeneous. The recurrence $T(n)=2T(n/2)$ has solution $\Theta (n)$ when $T(1)>0$ and the zero solution when $T(1)=0$ [S:5:893]. The merge recurrence escapes this case because of the $n-1$ term. So "the base case does not matter" holds for the recurrences in this chapter, not for every recurrence.

What the core hid. The core named the floors and ceilings in its closing paragraph, so it did not hide them. What it did not say is that the exact recurrence has two different sizes, that the asymptotic answer ignores them, and that a homogeneous recurrence can depend on its boundary condition. The first two change nothing at the level of the answer, and the third does not arise for merge sort, which is why the table still checks the closed form.

Where the tree breaks. A recursion tree is a tree only when the subproblems are disjoint. When they overlap, as they do for Fibonacci, the same subproblem appears in many branches, and summing the tree counts the same work many times. That is the subject of 5.5, and it is why the recursion tree is not a general tool.

Original sources. The merge-sort recurrence appears in Mathematics for Computer Science as $T_n=2T_{n/2}+n-1$, and the same section derives the closed form $n\log n-n+1$ by plug-and-chug [S:5:880][S:5:881]. The pattern behind the recurrence has its own name: divide the problem, solve the parts, combine the answers [S:1:49]. The recursion-tree method and its three cases are set out by Erickson [S:1:51]. The general solution is the Akra–Bazzi theorem, and the master theorem is its special case [S:5:893][S:5:895].

An open question. Integer multiplication now runs in $O(n\log n)$ time, from Harvey and van der Hoeven in 2019 [S:1:60]. Whether $n\log n$ is optimal is open. The asymptotic gain is invisible at practical sizes, since the newer methods become faster only for numbers with more digits than there are particles in the universe [S:1:60]. Evidence that would settle it: a lower bound proving that no procedure can do better, or a procedure that beats $n\log n$ by a factor growing with $n$.

A frontier result. Karatsuba's trick computes the middle coefficient from the other two using one extra multiplication, which replaces four recursive multiplications with three and moves the cost from $n^2$ to $n^{{\log }_{2}3}$ [S:1:59]. It is the cleanest demonstration that the number of subproblems, and not the work per level, sets the exponent. The same tree argument that gave $\Theta (n\log n)$ for merge sort produces the new exponent with no extra machinery [S:1:58].

What to read next. Read section 21.4 of Mathematics for Computer Science for Akra–Bazzi and for the floors-and-ceilings argument [S:5:893]. Read the master theorem in the same section and the proof that it follows from Akra–Bazzi. Then read the section on fast multiplication in Erickson for the sequence from Karatsuba to the 2019 result [S:1:59][S:1:60].