A Systematic Approach to Algorithms

Vijay K. Garg · The University of Texas at Austin

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:

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 in $O(n \log n)$: pre-sort by $x$-coordinate, 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. The strip scan is $O(n)$ thanks to a beautiful geometric argument: any candidate pair that improves $\delta$ has its $y$-coordinates within $\delta$, so each strip point compares against only a constant number of neighbours.

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

The LLP perspective

Divide-and-conquer programs are not naturally fixed-point algorithms; they are recipes that compose recursive calls with a combine step. However, several divide-and-conquer problems admit lattice-linear reformulations that recover the correct answer as the least fixed point of a forbidden/advance rule. These reformulations do not match the asymptotic running time of the sharpest divide-and-conquer algorithms, but they expose the parallelism in the problem and give a uniform template that a parallel scheduler can exploit.

Three problems from this chapter have natural LLP reformulations:

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.

LLP-NearestNeighbor

For each point $p_j$, the vector $G[j]$ holds an upper bound on the distance from $p_j$ to its nearest neighbour. The forbidden condition fires when some other point $k$ is closer than $G[j]$; the advance sets $G[j]$ to the exact minimum distance over all other points. At the least fixed point, $G[j] = \min_{k \neq j} d(p_j, p_k)$ for every $j$, and the global nearest-pair distance is $\min_j G[j]$.

Time complexity: $O(n^2)$, where $n$ is the number of points.

Lattice-linear on the reverse-ordered real lattice: lowering $G[j]$ never invalidates other resolved indices. Total work $O(n^2)$; with $n$ processors, $O(n)$ parallel time.

LLP-CountInversions

Given an array $A[0..n{-}1]$, $G[j]$ counts the number of indices to the left of $j$ whose value is strictly greater than $A[j]$. Index $j$ is forbidden when $G[j]$ is strictly less than the true count; the advance sets $G[j]$ to the exact count. The total number of inversions is $\sum_j G[j]$.

Time complexity: $O(n^2)$, where $n$ is the size of the array.

Each index is advanced at most once and the advance scans $j$ left neighbours, so total work is $O(n^2)$. With $n$ processors all indices can advance in parallel for $O(n)$ parallel time.

LLP-ConvexHull

The convex hull of a point set is expressed on a Boolean lattice. $G[j] = 1$ means $p_j$ is a hull candidate; $G[j] = 0$ means it has been eliminated. A point $p_j$ is forbidden when $G[j] = 1$ and $p_j$ lies strictly inside a triangle formed by three other hull candidates. The advance sets $G[j] := 0$. At the least fixed point, $G$ is the characteristic vector of the convex hull.

Time complexity: $O(n^4)$, where $n$ is the number of points.

Each forbidden check considers $O(n^3)$ triangles, for $O(n^4)$ total work — far worse than the $O(n \log n)$ divide-and-conquer algorithm. The LLP formulation returns the hull as a membership vector; recovering the cyclic vertex order requires a post-processing step.

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.

LLP-ConvexHull

Eliminate interior points: $j$ is forbidden when it lies inside some triangle formed by three other hull-candidate points; the advance removes it from the candidate set.

// LLP-ConvexHull: eliminate interior points to find convex hull membership.
// px[j], py[j] are x,y coordinates of point j.

class LLPConvexHull {
  void LLPConvexHull(double[] px, double[] py) {
    boolean[] G = true;
    forbidden (j) : G[j] && isInterior(j, px, py, G) =>
      advance : G[j] = false;
  }

  boolean isInterior(int j, double[] px, double[] py, boolean[] G) {
    int i = 0;
    while (i < px.length) {
      if (i != j && G[i]) {
        int k = i + 1;
        while (k < px.length) {
          if (k != j && G[k]) {
            int l = k + 1;
            while (l < px.length) {
              if (l != j && G[l]) {
                if (insideTriangle(px, py, j, i, k, l)) {
                  return true;
                }
              };
              l = l + 1;
            }
          };
          k = k + 1;
        }
      };
      i = i + 1;
    };
    return false;
  }

  boolean insideTriangle(double[] px, double[] py, int j, int a, int b, int c) {
    double d1 = sign(px[j], py[j], px[a], py[a], px[b], py[b]);
    double d2 = sign(px[j], py[j], px[b], py[b], px[c], py[c]);
    double d3 = sign(px[j], py[j], px[c], py[c], px[a], py[a]);
    boolean hasNeg = (d1 < 0.0) || (d2 < 0.0) || (d3 < 0.0);
    boolean hasPos = (d1 > 0.0) || (d2 > 0.0) || (d3 > 0.0);
    return !hasNeg || !hasPos;
  }

  double sign(double x1, double y1, double x2, double y2, double x3, double y3) {
    return (x1 - x3) * (y2 - y3) - (x2 - x3) * (y1 - y3);
  }
}

Plain text: LL · Java

LLP-CountInversions

Count inversions to the left of each index: $j$ is forbidden when $G[j]$ is less than the number of elements to the left of $j$ that are larger than $A[j]$.

// LLP-CountInversions: count inversions to the left of each index.

class LLPCountInversions {
  void LLPCountInversions(int[] A) {
    int[] G = 0;
    forbidden (j) : G[j] < countLeft(A, j) =>
      advance : G[j] = countLeft(A, j);
  }

  int countLeft(int[] A, int j) {
    int count = 0;
    int i = 0;
    while (i < j) {
      if (A[i] > A[j]) { count = count + 1; };
      i = i + 1;
    };
    return count;
  }
}

Plain text: LL · Java

LLP-NearestNeighbor

Find the nearest-neighbor distance for each point: $j$ is forbidden when $G[j]$ exceeds the actual nearest distance; the advance corrects it.

// LLP-NearestNeighbor: find nearest neighbor distance for each point.
// px[j], py[j] are x,y coordinates of point j.

class LLPNearestNeighbor {
  void LLPNearestNeighbor(double[] px, double[] py) {
    double[] G = infinity;
    forbidden (j) : G[j] > nearestDist(px, py, j) =>
      advance : G[j] = nearestDist(px, py, j);
  }

  double nearestDist(double[] px, double[] py, int j) {
    double best = infinity;
    int k = 0;
    while (k < px.length) {
      if (k != j) {
        double d = dist(px, py, j, k);
        if (d < best) { best = d; }
      };
      k = k + 1;
    };
    return best;
  }

  double dist(double[] px, double[] py, int j, int k) {
    double dx = px[j] - px[k];
    double dy = py[j] - py[k];
    return dx * dx + dy * dy;
  }
}

Plain text: LL · Java