Divide and Conquer

Divide and conquer solves a problem by splitting it into smaller instances of the same problem, solving those recursively, and combining their answers. Merge sort, quicksort and binary search are the familiar examples. This note states the paradigm, shows how its running time becomes a recurrence, and works through the other standard examples: the minimum and maximum together, fast exponentiation, the maximum subarray, and fast integer and matrix multiplication.

The pattern pays off when the combine step is cheap compared with solving the whole problem directly, or when the split lets us avoid work (binary search discards half; Strassen's method uses 7 recursive products instead of 8).

If dividing and combining together cost $f(n)$, the running time satisfies

The master theorem compares $f(n)$ with $n^{\log_b a}$, the number of leaves of the recursion tree. Two ways to make an algorithm faster follow directly: reduce $a$ (fewer recursive calls, as in Karatsuba and Strassen) or reduce $f(n)$ (a cheaper combine).

For binary search, merge sort and quicksort see Searching, Merge Sort and Quicksort.

Pseudocode uses 1-based arrays, <- for assignment and A[i..j] for the subarray from position $i$ to position $j$.

Finding the maximum alone needs $n - 1$ comparisons, and the minimum alone another $n - 1$. Divide and conquer finds both with fewer:

The comparison count satisfies $C(1) = 0$, $C(2) = 1$ and $C(n) = 2C(n/2) + 2$. For $n = 2^k$ with $k\ge1$ ($n\ge2$), the solution is exactly

Proof by unrolling: there are $n/2$ leaves of size 2 costing 1 each, and $n/2 - 1$ internal combines costing 2 each, so $C(n) = n/2 + 2(n/2 - 1) = 3n/2 - 2$. This matches the lower bound $\lceil 3n/2 \rceil - 2$ for finding both, which is derived in Comparison of Sorting Algorithms. For $n$ not a power of 2 the halving version (left part $\lceil n/2 \rceil$ elements, as floor((i + j) / 2) gives) can use more; the pairwise (non-recursive) method that compares elements in pairs always achieves $\lceil 3n/2 \rceil - 2$.

The loss appears when a halving step creates two parts of odd size: for $n = 6$ the split $3 + 3$ costs $3 + 3 + 2 = 8$, while $2 + 4$ costs $1 + 4 + 2 = 7$. A question that says "$n$ is a power of 2" avoids the issue; otherwise ask which split the code uses.

$M(n) = M(\lfloor n/2 \rfloor) + 1$ or $+2$, so $\Theta(\lg n)$ multiplications instead of $n - 1$. Exactly, POWER uses $\lfloor \lg n \rfloor$ squarings plus one extra multiplication for each 1 bit of $n$ except the leading one: $\lfloor \lg n \rfloor + \nu(n) - 1$ multiplications, where $\nu(n)$ is the number of 1 bits. For $n = 13 = 1101_2$: $3 + 3 - 1 = 5$ multiplications ($x^{13}$ from $x^6$, $x^6$ from $x^3$, $x^3$ from $x$).

Problem. Given $A[1..n]$ with positive and negative values, find indices $i \le j$ maximising $A[i] + \cdots + A[j]$.

Split at $mid$. The best subarray lies entirely in the left half, entirely in the right half, or crosses the midpoint. A crossing subarray is a best suffix of $A[low..mid]$ followed by a best prefix of $A[mid+1..high]$, found in linear time:

$T(n) = 2T(n/2) + \Theta(n) = \Theta(n \lg n)$. With all entries negative, the answer is the single largest entry (the problem as stated requires a non-empty subarray).

Related material. Kadane's scan solves the same problem in $\Theta(n)$ by keeping the best sum ending at each position; it is dynamic programming, not divide and conquer, and is commonly presented together with this algorithm.

To multiply two $n$-digit numbers, write $x = x_1 10^{n/2} + x_0$ and $y = y_1 10^{n/2} + y_0$. Then

which needs four half-size products and gives $T(n) = 4T(n/2) + \Theta(n) = \Theta(n^2)$, no better than school multiplication. Karatsuba's observation is that the middle term equals $(x_1 + x_0)(y_1 + y_0) - x_1 y_1 - x_0 y_0$, so three products suffice: $T(n) = 3T(n/2) + \Theta(n) = \Theta(n^{\lg 3})$.

Counting one-digit products, $M(n) = 3M(n/2)$ with $M(1) = 1$ gives $M(n) = 3^{\lg n} = n^{\lg 3}$: 9 for 4-digit numbers and 81 for 16-digit numbers, against $n^2 = 16$ and 256 for the four-product split (ignoring the extra digit that the sums $x_1 + x_0$ may carry).

Example: $1234 \times 5678$ with $x_1 = 12$, $x_0 = 34$, $y_1 = 56$, $y_0 = 78$: $x_1 y_1 = 672$, $x_0 y_0 = 2652$, $(12 + 34)(56 + 78) = 46 \times 134 = 6164$, middle term $6164 - 672 - 2652 = 2840$, and $672 \cdot 10^4 + 2840 \cdot 10^2 + 2652 = 7006652$.

Splitting $n \times n$ matrices into four $n/2 \times n/2$ blocks gives 8 block products and $T(n) = 8T(n/2) + \Theta(n^2) = \Theta(n^3)$. Strassen's method forms 7 block products from sums and differences of blocks, using 18 block additions and subtractions in total, so

The exact seven products are not needed for the running-time analysis here; the recurrence, the count 7 and the result $n^{\lg 7}$ are.

$A = 13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7$, $low = 1$, $high = 16$, $mid = 8$.

The answer is the largest of $20$, $25$ and $43$: $A[8..11] = 18 + 20 - 7 + 12 = 43$.

The last row is a warning: when the combine step dominates, splitting gains nothing.

Common misconceptions.