Divide & Conquer

Divide and conquer is not one algorithm — it is a design pattern, and most of the fastest algorithms you already know wear it. The shape is always three steps: divide the problem into smaller copies of itself, conquer each one recursively (stopping at a base case small enough to answer directly), then combine the partial answers into the whole.

The quiet requirement that makes it work is that the subproblems are independent — solving one does not depend on solving another. That independence is what lets you split the work, and (as we will see) what lets you parallelise it.

You have met the pattern already. Binary search is the easy case: divide by comparing to the middle, conquer by recursing into the one half that can contain the target, and the combine step is nothing — the recursive call returns the answer directly. That is why it is O(log n). Merge sort uses all three steps for real: divide at the midpoint, sort each half, then combine by merging two sorted halves in O(n) — and that O(n) combine, repeated over log n levels, is exactly the O(n log n).

A less obvious case: maximum subarray

Given an array that may hold negatives, find the contiguous stretch with the largest sum. Split at the midpoint, and the best subarray is one of three things: entirely in the left half, entirely in the right half — or straddling the midpoint.

The two recursive calls handle the left-only and right-only cases; the combine step handles the crossing case in O(n) by expanding outward from the midpoint. The best of the three is the answer — O(n log n), better than the naive O(n²).

Fast exponentiation

Computing x to the power n looks like it needs n multiplications. Divide and conquer cuts it to O(log n) with one observation: if n is even, xⁿ = (x^(n/2))²; if odd, xⁿ = x · x^(n−1). Each step at least halves the exponent.

def pow_fast(x, n):
    if n == 0:
        return 1, 0                       # value, multiplication count
    if n % 2 == 0:
        half, ops = pow_fast(x, n // 2)
        return half * half, ops + 1       # one squaring
    rec, ops = pow_fast(x, n - 1)
    return x * rec, ops + 1

for n in [10, 50, 200, 1000, 5000]:
    _, ops = pow_fast(2, n)
    print(f"x**{n}: naive needs {n} multiplications, fast needs {ops}")

x**10: naive needs 10 multiplications, fast needs 5
x**50: naive needs 50 multiplications, fast needs 8
x**200: naive needs 200 multiplications, fast needs 10
x**1000: naive needs 1000 multiplications, fast needs 15
x**5000: naive needs 5000 multiplications, fast needs 17

Fifteen multiplications for x¹⁰⁰⁰ instead of a thousand — and the gap only widens, because it is O(log n) against O(n). (Karatsuba multiplication is the same trick on big numbers: split each at the midpoint, recurse on the pieces, and combine cleverly to use three sub-multiplications instead of four, dropping long multiplication from O(n²) to about O(n^1.585).)

Recurrences and where the work goes

Every divide-and-conquer cost is captured by a recurrence, T(n) = a·T(n/b) + f(n): you make a recursive calls, each on a piece of size n/b, plus f(n) work to divide and combine. The Master Theorem answers it, and you only need its intuition — which level of the recursion does most of the work? Picture the recursion as a tree. If the split-and-combine work f(n) grows slower than the number of leaves, the leaves dominate; if it grows faster, the root dominates; and if they grow at the same rate, every level does equal work and you pick up an extra log factor.

Merge sort is the equal case: a = b = 2 and f(n) = n, so each of the log n levels contributes the same O(n) of merging — O(n log n). Binary search is also equal, but with O(1) per level across log n levels — O(log n).

Practice