Divide & conquer

Divide and conquer is recursion with a particular shape. Each call does three things:

Binary search is the smallest example: it divides the range in two, conquers only the half that can hold the target, and has nothing to combine. Finding the largest item is the next one up.

The largest item of a list is the larger of the left half's largest and the right half's largest. A one-item range is its own largest item. That is a complete divide-and-conquer algorithm:

Eight items made 15 calls: 8 one-item base cases and 7 combines, one for each pair of answers joined. A loop would also do 7 comparisons. Divide and conquer doesn't make this problem faster; it is here because the shape is easy to see. The payoff comes when combining two sorted halves, or skipping a half, beats working on the whole.

Computing x¹⁰ by multiplying 10 copies of x takes 9 multiplications. But x¹⁰ = x⁵ × x⁵: compute x⁵ once, square it, and you have halved the problem. For an odd power, multiply in one more x: x⁵ = x² × x² × x.

Each call halves n, so the depth is about log₂ n, and each level does one or two multiplications. Raising a number to the millionth power takes about 20 levels instead of a million multiplications. The two halves were identical, so solving one was enough.

The best run in a range is either entirely in the left half, entirely in the right half, or crosses the middle. The first two are smaller copies of the problem. The crossing one is cheap: the best run ending at the middle plus the best run starting just after it, found by walking outward. That is T(n) = 2T(n ÷ 2) + O(n): O(n log n). A single pass solves this problem in O(n) (Dynamic programming: basics); here it shows how the crossing case works.

The running time of a divide-and-conquer algorithm is easiest to write the way the algorithm itself is written: in terms of smaller copies of itself. That equation is a recurrence. For the largest item, T(n) = 2T(n ÷ 2) + O(1): two half-size calls plus a constant amount of combining.

Read the totals off the recursion tree. With halves, it is about log₂ n levels deep. If the work at each level adds up to O(n), as when every item is touched once per level, the total is O(n log n). If only one call is made per level and it does constant work, the total is just the depth, O(log n).

The next page uses this shape twice. Merge sort splits the list in half, sorts both halves and merges them, which is the T(n) = 2T(n ÷ 2) + O(n) row: O(n log n). Quicksort does the splitting work first, around a chosen item, and then needs no combining at all. Its risk is the last row of the table: a bad split, repeated, makes it O(n²).