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 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 neighbors — but finding those neighbors 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 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, counting inversions, and planar convex hull — 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. These reformulations also appear in the parallel edition of the book, presented there 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$. Forbidden detects a stale count; advancing 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. Forbidden detects a distance that hasn't yet reached its true minimum; advancing 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.

LLP-ConvexHull

$G[j]$ is true while point $j$ is still a candidate for the hull. Forbidden detects that $j$ lies strictly inside the triangle formed by three other surviving candidates (so $j$ cannot possibly be a hull vertex); advancing simply marks it interior. Each forbidden check examines every triple of surviving points, an $O(n^3)$ cost per check, considerably more than the classical $O(n \log n)$ divide-and-conquer hull above — again prioritizing the forbidden/advance formulation over efficiency.

Time complexity: $O(n^4)$ in the worst case ($O(n)$ points each eliminated via an $O(n^3)$ check), 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.

Looking ahead

Divide-and-conquer recurrences underpin Chapter 10 (dynamic programming, where overlapping subproblems force memoization), 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.