Chapter 9. Divide and Conquer
Lattice-linear reformulations of classical divide-and-conquer problems.
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 neighbors)
Given $n$ points in the plane, find the pair with the smallest Euclidean distance. Naive $O(n^2)$. Divide-and-conquer: pre-sort once outside the recursion, by $x$-coordinate and by $y$-coordinate ($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 neighbors — and finding those neighbors needs the strip in $y$-order, which each call inherits: it splits its own $y$-ordered index list between the two halves in $O(n)$ and reads the strip off it already sorted. No level ever re-sorts, so the combine step is $O(n)$ and the recurrence is $T(n) = 2T(n/2) + O(n)$, solving to $T(n) = O(n \log n)$ — the classical refinement noted at the end of the book's analysis, which re-sorted the strip at every level for $T(n) = O(n \log^2 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 expressed as forbidden/advance loops; they
are recipes that compose recursive calls with a combine step. Several divide-and-conquer
problems from this chapter — nearest neighbors and counting inversions — do
admit lattice-linear reformulations that recover the correct answer as the least vector
satisfying a forbidden/advance rule, reached once no index
remains forbidden. They are presented for the structural insight they offer rather than
for efficiency: each trades the classical divide-and-conquer time bound for a simpler,
uniform forbidden/advance rule.
LLP-CountInversions
$G[j]$ is the number of inversions $(i, j)$ with $i < j$ and $A[i] > A[j]$, i.e. how many larger elements precede index $j$. The program is written with ensure: it requires $G[j]$ to be at least that count, which is shorthand for a forbidden test that detects a stale count together with an advance that recomputes it by a direct left-to-right scan. Every index needs only one advance to reach its final value, but each advance recomputes the count from scratch in $O(n)$ time, so this reformulation is $O(n^2)$ overall — slower than the classical $O(n \log n)$ merge-and-count algorithm above, trading efficiency for the uniform forbidden/advance structure.
Time complexity: $O(n^2)$, where $n$ is the array length.
LLP-NearestNeighbor
$G[j]$ is the squared distance from point $j$ to its nearest neighbor among the other $n - 1$ points. The program is written with ensure: it requires $G[j]$ to be at most that minimum, which is shorthand for a forbidden test that detects a distance not yet down to its true minimum together with an advance that recomputes it by scanning every other point directly. As with LLP-CountInversions, the direct $O(n)$ recomputation per index gives $O(n^2)$ total time.
Time complexity: $O(n^2)$, where $n$ is the number of points.
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.
LLP predicates for this chapter
Each LLP program in this chapter defines a state vector $G$ and a
forbidden predicate; the algorithm runs until no $j$ is forbidden.
The table below lists, for each algorithm, what $G[i]$ represents and the
negation of the forbidden clause from the matching .llp source.
| Algorithm | $G[j]$ | Negation of the forbidden clause |
|---|---|---|
| LLP-CountInversions | $G[j]$ — number of inversions ending at index $j$ | $\forall j:\ G[j] \geq \bigl|\{\, i < j :\ A[i] > A[j] \,\}\bigr|$ |
| LLP-NearestNeighbor | $G[j]$ — squared distance from point $j$ to its nearest other point | $\forall j:\ G[j] \leq \min_{k \neq j} \mathrm{dist}^2(j, k)$ |
The first two are written as ensure clauses rather than explicit
forbidden/advance pairs, so the last column is $B$ itself — the condition that
holds exactly when no index is forbidden. LLP-NearestNeighbor is the one
descending search on this page: $G$ starts at $\infty$ and the
ensure bounds it from above, so its lattice is ordered by $\geq$.
Looking ahead
Divide-and-conquer recurrences underpin Chapter 10 (dynamic programming, where overlapping subproblems force memoization) and Chapter 11 (network flow, where augmenting-path methods recurse on residual graphs).