Chapter 9. Divide and Conquer

Fixed-point reformulations of classical divide-and-conquer problems on lattices.

This page: LLP forms. View classical forms »

Setting

A divide-and-conquer algorithm reduces a problem of size $n$ to a small number of independent subproblems of size $n/b$, solves each recursively, and combines the answers in $O(f(n))$ time. The combine step often dominates and the running time satisfies a recurrence of the form $T(n) = a \cdot T(n/b) + f(n)$. The recursive subproblems are independent, so a parallel evaluator can run them concurrently — captured in LL by Dijkstra-style parallel composition $[ A \, [] \, B ]$.

The Master Theorem

Let $a \geq 1$, $b > 1$, and $c \geq 0$, and suppose that $T(n) = a\,T(n/b) + O(n^c)$ with $T(1) = O(1)$. Then

$$ T(n) = \begin{cases} O(n^{\log_b a}) & \text{if } c < \log_b a, \\ O(n^c \log n) & \text{if } c = \log_b a, \\ O(n^c) & \text{if } c > \log_b a. \end{cases} $$

Here $a$ is the number of sub-problems, $b$ is the factor by which the sub-problem size shrinks, and $O(n^c)$ is the cost of work done outside the recursive calls.

Applications:

Merge Sort. $T(n) = 2T(n/2) + O(n)$: $a = 2$, $b = 2$, $c = 1 = \log_2 2$; case 2 gives $T(n) = O(n \log n)$.
Binary Search. $T(n) = T(n/2) + O(1)$: $a = 1$, $b = 2$, $c = 0 = \log_2 1$; case 2 gives $T(n) = O(\log n)$.
Strassen. $T(n) = 7T(n/2) + O(n^2)$: $a = 7$, $b = 2$, $c = 2 < \log_2 7 \approx 2.81$; case 1 gives $T(n) = O(n^{2.81})$.
Karatsuba. $T(n) = 3T(n/2) + O(n)$: $a = 3$, $b = 2$, $c = 1 < \log_2 3 \approx 1.58$; case 1 gives $T(n) = O(n^{1.58})$.

Closest pair of points (Euclidean nearest neighbours)

Given $n$ points in the plane, find the pair with the smallest Euclidean distance. Naive $O(n^2)$. Divide-and-conquer: pre-sort by $x$-coordinate once (outside the recursion, $O(n \log n)$), recurse on the left and right halves, then scan a "strip" of width $\delta$ (the minimum distance found in either half) around the median $x$-line. Within the strip, any candidate pair that improves $\delta$ has $y$-coordinates within $\delta$, so each strip point compares against only a constant number of neighbours — but finding those neighbours requires the strip sorted by $y$-coordinate at each recursive level, which costs $O(n \log n)$ per level. This gives the recurrence $T(n) = 2T(n/2) + O(n \log n)$, solving to $T(n) = O(n \log^2 n)$. The classical $O(n \log n)$ algorithm avoids the repeated re-sort by maintaining $y$-sorted order through the recursion (as in Mergesort), reducing the combine step to $O(n)$.

Counting inversions

An inversion in an array $A$ is a pair $(i, j)$ with $i < j$ and $A[i] > A[j]$. The number of inversions measures how far $A$ is from sorted. The merge step of MergeSort counts cross-half inversions for free: when we pull from the right half, every element still pending in the left half is the larger half of an inversion. Total time: $O(n \log n)$.

Other classical examples

Planar Convex Hull. Divide the points by $x$-coordinate; recursively hull the halves; merge by computing the upper and lower tangents in $O(n)$. Total $O(n \log n)$.
Karatsuba multiplication. Multiplies two $n$-digit integers in $\Theta(n^{\log_2 3}) \approx \Theta(n^{1.585})$ time using three half-size multiplications instead of four.
Strassen multiplication. Multiplies two $n \times n$ matrices in $\Theta(n^{\log_2 7}) \approx \Theta(n^{2.81})$ time using seven half-size multiplications instead of eight.
Fast Fourier Transform. Evaluates a degree-$n$ polynomial at the $n$-th roots of unity in $\Theta(n \log n)$ via the Cooley-Tukey decomposition, enabling $\Theta(n \log n)$ polynomial multiplication.

The LLP perspective

Divide-and-conquer programs are not naturally fixed-point algorithms; they are recipes that compose recursive calls with a combine step. Several divide-and-conquer problems from this chapter — nearest neighbours, counting inversions, and planar convex hull — do admit lattice-linear reformulations that recover the correct answer as the least fixed point of a forbidden/advance rule (LLP-NearestNeighbor, LLP-CountInversions, and LLP-ConvexHull). These reformulations are part of the parallel edition of the book; this companion page follows the sequential edition, which does not include them, so no runnable demo is shown here for these three.

Integer multiplication (Karatsuba) and matrix multiplication (Strassen) compute a uniquely determined output via algebraic identities that reduce recursive multiplications; they do not search a lattice for a predicate-satisfying element and consequently do not admit natural LLP reformulations either way.

Looking ahead

Divide-and-conquer recurrences underpin Chapter 10 (dynamic programming, where overlapping subproblems force memoisation), Chapter 11 (network flow, where augmenting-path methods recurse on residual graphs), and the parallel-prefix / tree-contraction primitives that appear throughout the book's parallel chapters.