Divide and conquer

Three problems. Sort 19,073 earthquakes by depth. Find their median depth. Multiply the two halves of the number 300!, the products 1·2·…·150 and 151·…·300. All three are solved by one technique: cut the problem into parts, solve the parts the same way and glue the answer together. But they cost differently. Below is a cross-section of each one's recursion tree: a bar is how much work was done on a level, and the partitions in a bar are that level's subproblems. Switch problems and move the size.

There are three pictures, and they are not alike. For sorting the levels are almost the same: each costs about 19 thousand comparisons, because on every level the whole catalogue is merged, only in pieces of different lengths. There are fifteen levels, and in all it comes to 245,169 comparisons, roughly n log₂ n. For the median the bars melt from top to bottom: quickselect continues in only one part, and the work is concentrated at the top; the whole search costs 57,124 comparisons, three times the number of earthquakes. For multiplication it is the other way round: each level is one and a half times dearer than the previous one, and the main work is at the bottom, in the leaves, where single digits are multiplied.

Try to break the picture. For the median turn on the sorted data with the first element as pivot, and the tree stretches into a column of hundreds of levels. For multiplication turn on four products instead of three, and each level becomes twice as dear as the previous one. Both breakages are explained by one theorem, and that is where we are heading.

The idea

A problem of size n is cut into a subproblems of the same kind of size n/b, which are solved the same way until they become very small, and the answers are glued together. If cutting and gluing cost f(n), the time obeys the equation T(n) = a·T(n/b) + f(n), and its solution tells where in the recursion tree the main work lies.

The three steps, divide, solve, glue, are in every algorithm of this kind, but the weight falls differently. Merge sort cuts blindly, in half, and all its thinking is in the gluing. Quicksort is the opposite: it thinks while cutting and has nothing to glue. Binary search and quickselect solve only one of the parts. Karatsuba wins by making do with three subproblems where four suggest themselves. Here are the parameters of the equation for the best-known algorithms of this kind:

For the technique to work, three things are needed. The subproblems must be of the same kind as the original, otherwise the recursion has nothing to stand on. They must be noticeably smaller, several times, not by one. And gluing the answers must be cheaper than solving the problem anew. Where this is violated, the technique stops helping; a separate section below is given to such cases.

The recursion tree

Draw all the calls as a tree. At the root is the problem of size n, each node has a children, and the size falls by a factor of b with each level. This is the recursion tree, and the time of the algorithm is the sum of the work of all its nodes. It is more convenient to add it up by levels. On level i there are aⁱ subproblems of size n/bⁱ, and if gluing a problem of size m costs m^d, the level as a whole costs

$$a^i \cdot \left(\frac{n}{b^i}\right)^{d} = n^d \cdot \left(\frac{a}{b^d}\right)^{i}.$$

The work of the levels is a geometric progression with ratio q = a/b^d, and everything is decided by this ratio: each level is dearer than the previous one, cheaper, or the same. In the first scene this is visible right in the bars. For sorting a = 2, b = 2, d = 1, and q = 1: the bars are equal. For the median there is one subproblem, and q = 1/2: the bars halve. For Karatsuba q = 3/2, for four products q = 2: the bars grow.

The real bars are not quite even, and that is instructive. The lower levels of sorting are cheaper than the upper ones: short pieces merge in fewer than one comparison per element, because one of the pieces often runs out first. The median melts unevenly: on real data the pivot is sometimes badly placed, and after the very first partition the piece shrank by only a hundred earthquakes out of 19 thousand. The equation describes the tree as a whole, not each of its nodes.

The master theorem

The proof gives more than the statement: it says where to look to speed an algorithm up. In the first case all the time goes into gluing at the root, and that is what must be sped up. In the third gluing costs almost nothing, and we pay for the number of leaves n^{log_b a}: Karatsuba reduced a from four to three and thereby changed the exponent from 2 to log₂ 3 ≈ 1.585. In the second case both factors matter. For powers of two the equations are solved exactly: T(n) = T(n/2) + n gives 2n − 1, the equation 2T(n/2) + n gives n log₂ n + n, and 3T(n/2) + n gives 3n^{log₂ 3} − 2n (all three with T(1) = 1).

Let us check the theorem by measurement. Below are the same five programs on problems of growing size; the axes are logarithmic, so a power of n looks like a straight line, and its slope is the exponent.

The slopes match the prediction: about one for the median, a little over one for merge sort, which is how n log n looks on logarithmic axes, about 1.6 for Karatsuba, and about two for four products and for the broken median.

Where the theorem is silent

The theorem does not cover all equations, and it is useful to know its limits.

The gluing is not a power. If f(n) = n log n with a = b = 2, no case fits: f grows faster than n but slower than any n^1+ε. Count by levels: level i costs n log(n/2ⁱ), and the sum over log n levels gives Θ(n log² n). This is what happens with the closest pair of points if the strip is sorted anew in each call; by sorting the points in advance, the gluing is made linear and we are back to n log n. A more general form of the theorem allows any f(n) separated from n^{log_b a} by a power, and in the third case also requires the gluing one level down to be noticeably cheaper: a·f(n/b) ≤ c·f(n) for some c < 1.

Parts of different sizes. Median of medians, quickselect with a guarantee, solves a problem on a fifth and a problem on seven tenths: T(n) ≤ T(n/5) + T(7n/10) + n. The theorem with a single b does not fit here, but the recursion tree answers at once: the total size of the subproblems on each level is at most 1/5 + 7/10 = 9/10 of the previous one, the work of the levels is a decreasing progression, and all together it is Θ(n). The general answer for such equations was given by Mohamad Akra and Louay Bazzi in 1998.

Parts not several times smaller. The broken median from the first scene cuts off one element at a time: T(n) = T(n − 1) + n. There is no b > 1 here, the depth of the tree is n, not log n, and the sum n + (n − 1) + … gives Θ(n²). On a thousand sorted earthquakes the listing below counted 501 levels and 375,750 comparisons, almost exactly 3/8 · 1000².

Code

The three problems of the first scene as programs. Each reports how much work it did on which level: sorting the comparisons while merging, quickselect the comparisons with the pivot, multiplication the length of the numbers passing through additions and shifts in each node, and in the leaves the multiplications of digits. The numbers are added digit by digit in lists, without built-in long arithmetic, so that its work can be seen.

Karatsuba, three products: 263 and 352 digits of 300! (digits handled)
  level  subproblems       work  next/this
      0            1        352      1.50
      1            3        528      1.50
      2            9        794      1.51
      3           27       1197      1.51

Karatsuba multiplied numbers of 263 and 352 digits in 21,897 digit multiplications. Long multiplication would have spent 263 · 352 = 92,576, and halving without the trick 203,776: cutting by itself gives nothing, and because the lengths of the halves have to be aligned it comes out even more than long multiplication. The gain comes only from the third product instead of the fourth.

What the technique itself costs

The master theorem gives the time, but algorithms of this kind have three more cost items about which it is silent.

Memory for recursion. The stack holds one branch of the tree, that is, log_b n frames if the parts shrink several times. For a million elements and b = 2 that is twenty frames. But if the parts shrink by one, as with the broken median or quicksort on an unlucky input, the depth becomes n, and Python stops the recursion at around a thousand levels. Hence the rule from quicksort: recurse into the smaller part and handle the larger one in a loop; then the depth is at most log₂ n. Beyond the stack there may be memory for gluing: merge sort keeps a buffer of n elements.

Small subproblems. The bottom of the tree has the most nodes, and the overheads there, a function call, slicing, allocating memory, cost more than the useful work. So real implementations take the recursion not down to one element but to a threshold and below it solve the simple way: merge sort switches to insertion on pieces of a few dozen elements (a measurement is in the article on merge sort), and Karatsuba in long arithmetic libraries switches to long multiplication on numbers of a few dozen machine words (details are in the article on Karatsuba multiplication). The threshold does not change the asymptotics, but it changes the constant factor several times.

Parallelism. The subproblems are independent and can be given to different cores. With unlimited cores the time is determined not by the sum of the work but by the longest chain of dependencies, one node on each level. For merge sort that is the gluing at the root in Θ(n), so parallel merging is itself split into parts; for Karatsuba multiplication the three subproblems are independent and can be computed at the same time on each level.

When the technique does not help

The subproblems repeat. The recursion F(n) = F(n − 1) + F(n − 2) looks like divide and conquer, but its subproblems overlap: F(n − 2) is computed both from the root and from F(n − 1), and the call tree grows exponentially. When the same subproblems come up again and again, they must be remembered: that is memoisation and dynamic programming. Divide and conquer is good when the parts do not overlap.

The gluing is expensive. The median of the catalogue cannot be glued from the medians of the halves: the median of the whole data may coincide with neither of them, and to find it one still has to look at the data as a whole. That is why quickselect cuts not by position but by the value of the pivot, so that the answer is guaranteed to lie in one part and there is nothing to glue. The right cut is half the success.

Too many parts. Four products of halves give q = 2, and the recursion tree costs as much as long multiplication: cutting shifted the work into the leaves and saved nothing. The technique wins only if a can be made smaller than the obvious b² or b³: that is what Karatsuba did for numbers and Strassen for matrices.

Unequal parts. If a cut separates a piece of constant size, the depth becomes linear, and n log n turns into n²: this is the worst case of quicksort and the broken median from the scene. The cure is a random choice of pivot or the median of medians.

History

The technique was used long before it was named. John von Neumann described merge sort in 1945, Anatoly Karatsuba found multiplication with three products of halves in 1960 (the story of Kolmogorov's refuted conjecture is told in the course chapter), James Cooley and John Tukey published the fast Fourier transform in 1965, and Volker Strassen in 1969 matrix multiplication with seven products instead of eight. Each time the running time was derived separately.

A general way to solve such equations was described in 1980 by Jon Bentley, Dorothea Haken and James Saxe in the note “A general method for solving divide-and-conquer recurrences”: the recursion tree and the sum of work by levels, as in this article. Under the name “master theorem” the result entered the first edition of the textbook by Cormen, Leiserson and Rivest in 1990, and since then it has been taught in almost every algorithms course. Equations with parts of different sizes were solved by Akra and Bazzi in 1998.

Problems

In the first problem you build the quadtree of a real photograph for many thresholds at once; the brute-force solution recomputes each square anew, while a good one glues the answer from four quarters in constant time, exactly the difference between the second and third cases of the theorem. In the second problem divide and conquer builds the answer itself: tile a floor with a column using L-shaped tiles.