Divide and Conquer

MergeMerge sort's strategy — split the problem, solve the pieces, combine the results — generalises far beyond sorting into one of the most productive general-purpose algorithm design strategies in the field.

The General Strategy

EveryEvery divide-and-conquer algorithm follows the same three-step shape: divide the problem into smaller subproblems of the same kind, conquer each subproblem (recursively, if it's still too large to solve directly, or directly once it's small enough to be trivial), and combine the subproblems' solutions into a solution for the original problem. What makes this powerful rather than just "recursion with extra steps" is that the combine step is often cheap relative to solving the subproblem from scratch — merge sort's combine step is a single linear pass, far cheaper than re-sorting.

The Master Theorem

Divide-and-conquerDivide-and-conquer algorithms have a recurrence relation of the general form T(n) = a·T(n/b) + f(n): the problem is split into a subproblems, each of size n/b, plus f(n) work done outside the recursive calls (the divide and combine steps). The Master Theorem gives a direct way to read the algorithm's overall complexity off that recurrence, without solving it by hand each time, by comparing f(n) against n^(log_b a). Bentley, Haken, and Saxe first proved a general version of this result, covering the whole family of divide-and-conquer recurrences at once rather than solving each new algorithm's recurrence from scratch¹:

• If f(n) grows slower than n^(log_b a), the recursive calls dominate: T(n) = Θ(n^(log_b a))
• If f(n) grows at the same rate, an extra log factor appears: T(n) = Θ(n^(log_b a) · log n)
• If f(n) grows faster, the combine step dominates: T(n) = Θ(f(n))

Plugging merge sort's own recurrence in directly: it splits into a=2 subproblems, each of size n/2 (so b=2), with f(n) = n for the linear merge step. log_b a = log₂2 = 1, so n^(log_b a) = n¹ = n — exactly matching f(n)'s growth rate, landing in the middle case: T(n) = Θ(n · log n), which is exactly merge sort's known complexity, arrived at here from the recurrence alone rather than from a separate argument about halving and merging.

Application: Convex Hull

GivenGiven a set of points on a plane, the convex hull is the smallest convex polygon containing all of them — imagine stretching a rubber band around every point and letting it snap taut. A divide-and-conquer solution splits the points into a left half and a right half (by x-coordinate), recursively computes each half's convex hull, then combines the two hulls by finding the "upper bridge" and "lower bridge" — the pair of line segments that connect the two hulls while keeping every point still inside the combined shape — discarding whichever points from each half's hull end up strictly inside the merged hull rather than on its boundary. This achieves O(n log n), matching merge sort's shape exactly: split in half, solve recursively, and a combine step that's cheap relative to solving each half from scratch.

Application: Strassen's Matrix Multiplication

MultiplyingMultiplying two n×n matrices the standard way costs O(n³) — for each of the n² output entries, sum n products. Strassen showed this isn't actually optimal²: split each matrix into four n/2 × n/2 quadrants, and where the naive block-matrix approach would need 8 quadrant multiplications to combine them, Strassen found a way to compute the same result using only 7 quadrant multiplications, at the cost of some extra additions. Seven recursive multiplications of half-sized matrices, rather than eight, seems like a small saving, but recursion compounds it: solving the Master Theorem's recurrence with a=7, b=2 gives T(n) = Θ(n^(log₂7)) ≈ Θ(n^2.807) — asymptotically faster than the standard O(n³) algorithm, purely because one multiplication was eliminated at every level of the recursion, and that saving multiplies through every one of the log n recursive levels.

When It Doesn't Help

TheThe strategy earns its keep specifically when subproblems don't overlap and the combine step is genuinely cheap. When the same subproblem recurs many times across different branches of the recursion — as it does in a naive recursive Fibonacci or an unoptimised recursive knapsack solver — divide-and-conquer degenerates into redundant, exponential recomputation of the same answers, and dynamic programming's approach of caching subproblem solutions is the better fit instead.

References