Divide and Conquer, in depth: recursion trees, the master theorem, worked algorithms and making recursive code fast

What makes a problem divisible

Two properties decide whether divide and conquer fits. First, a sub-instance must be the same kind of problem as the whole, so the same function can solve it. Second, the sub-instances should be independent: solving one does not need the answer to another. When sub-problems overlap, so that the same smaller instance is reached along many paths, plain recursion repeats work exponentially and dynamic programming is the right tool: it is divide and conquer plus a table of solved sub-problems.

The combine step is where the design effort goes. Mergesort cuts at the midpoint and does linear work to merge. Quicksort does linear work to partition and nothing to combine. Binary search discards one half and recurses once. The split that makes the combine step cheapest usually wins.

Reading a recurrence off the code

The running time of a divide-and-conquer function satisfies a recurrence you can read straight from its structure: T(n) = a T(n/b) + f(n), where a is the number of recursive calls, n/b is the size of each, and f(n) is the cost of dividing plus combining at that level. Mergesort gives T(n) = 2T(n/2) + Theta(n); binary search gives T(n) = T(n/2) + Theta(1).

The recursion tree turns the recurrence into a sum: level i has aⁱ nodes each doing f(n/bⁱ) work, down to n^{log_b a} leaves. Shrinking level totals mean the root dominates, growing totals mean the leaves do, and equal totals multiply by the number of levels.

The master theorem, with worked cases

The master theorem packages those three situations. Let c_crit = log_b a, the exponent of the leaf count, and compare f(n) with n^c_crit:

• Leaves dominate. If f(n) = O(n^c) for some c below c_crit, then T(n) = Theta(n^c_crit).
• Balanced. If f(n) = Theta(n^c_crit log^k n) with k at least 0, then T(n) = Theta(n^c_crit log^k+1 n).
• Root dominates. If f(n) = Omega(n^c) for some c above c_crit, and f satisfies the regularity condition a f(n/b) <= k f(n) for some constant k < 1, then T(n) = Theta(f(n)).

The table carries the most useful lesson in the subject. Strassen and Karatsuba win by reducing a, the number of recursive calls, because in the leaf-dominated case the exponent is log_b a and the combine cost barely matters. In the root-dominated case only a cheaper combine helps. Uneven splits such as T(n) = T(n/3) + T(2n/3) + n fall outside the theorem; use the recursion tree (it gives Theta(n log n)) or the Akra-Bazzi method.

Worked example: counting inversions

An inversion is a pair of positions i < j with a[i] > a[j]; the count is the number of pairs two rankings disagree on, the basis of Kendall's tau. Checking every pair costs Theta(n²). Every inversion lies inside the left half, inside the right half, or across them, and cross inversions are easy to count while merging two sorted halves, giving Theta(n log n).

When the merge takes an element from the right half, that element is smaller than every element still waiting in the left half, and each of those forms one split inversion. So the merge adds len(left) - i to the count, and the combine step stays linear:

def sort_count(a):
    # Return (sorted copy of a, number of pairs i < j with a[i] > a[j]).
    n = len(a)
    if n <= 1:
        return list(a), 0
    mid = n // 2
    left, inv_l = sort_count(a[:mid])
    right, inv_r = sort_count(a[mid:])
    merged, i, j, split = [], 0, 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:          # <= keeps the sort stable and equal keys uncounted
            merged.append(left[i]); i += 1
        else:
            merged.append(right[j]); j += 1
            split += len(left) - i       # right[j] is smaller than every remaining left item
    merged.extend(left[i:]); merged.extend(right[j:])
    return merged, inv_l + inv_r + split

assert sort_count([3, 1, 2, 5, 4])[1] == 3     # (3,1), (3,2), (5,4)

Trace it on [3, 1, 2, 5, 4]. The left half [3, 1] contributes one inversion and sorts to [1, 3]. The right half [2, 5, 4] contributes one, (5, 4), and sorts to [2, 4, 5]. Merging: take 1 from the left; take 2 from the right while 3 is still waiting, adding 1; then 3, 4 and 5 add nothing. The total is 1 + 1 + 1 = 3, matching the three pairs listed in the assertion. The general lesson: make the combine cheap by having each call return extra structure, here a sorted copy.

Worked example: Karatsuba multiplication

Multiplying two n-digit numbers the schoolbook way is Theta(n²). Splitting each number into high and low halves, x = x1 B + x0 and y = y1 B + y0, gives xy = x1y1 B² + (x1y0 + x0y1) B + x0y0: four half-size products, which by the table is still Theta(n²). Karatsuba's observation is that the middle term equals (x1 + x0)(y1 + y0) - x1y1 - x0y0, so three products suffice. Dropping a from 4 to 3 changes the exponent to log2 3, about 1.585.

def karatsuba(x, y, cutoff=64):
    # Multiply non-negative ints; below the cutoff the schoolbook method wins.
    if x.bit_length() <= cutoff or y.bit_length() <= cutoff:
        return x * y
    m = max(x.bit_length(), y.bit_length()) // 2
    x1, x0 = x >> m, x & ((1 << m) - 1)          # x = x1*2^m + x0
    y1, y0 = y >> m, y & ((1 << m) - 1)
    z2 = karatsuba(x1, y1, cutoff)
    z0 = karatsuba(x0, y0, cutoff)
    z1 = karatsuba(x1 + x0, y1 + y0, cutoff) - z2 - z0   # one product instead of two
    return (z2 << (2 * m)) + (z1 << m) + z0

The cutoff matters as much as the recursion: the extra additions and shifts cost more than they save on small numbers, so real implementations switch to schoolbook multiplication below a benchmarked threshold and to Toom-Cook or FFT-based methods for very large inputs. Big-integer libraries already do this, so treat the code as a teaching model; Strassen applies the same trick to matrix blocks, saving one of eight block products per level.

Unbalanced splits and guaranteed pivots

The analysis above assumes the split is proportional. When it is not, the bound collapses. Quicksort that always picks the first element as the pivot, run on already sorted input, splits n into 0 and n - 1, giving T(n) = T(n - 1) + n = Theta(n²) and a recursion depth of n. Any constant-fraction split, even 1 to 9, keeps the total Theta(n log n), which is why random pivots work.

When you need a guarantee rather than an expectation, you can pay for a good split. Median of medians finds the k-th smallest element in worst-case linear time: split into groups of five, take each group's median, recursively find the median of those medians, and use it as the pivot. That pivot is guaranteed to have at least roughly 30 percent of the elements on each side, giving T(n) <= T(n/5) + T(7n/10) + O(n), which is linear because 1/5 + 7/10 is less than 1. In practice randomised quickselect is faster, and libraries fall back to a guaranteed method only when recursion goes too deep.

Making recursive code fast

Asymptotics decide which algorithm to use; constants decide how fast it runs. Four habits cover most of the gap between textbook recursion and production code:

• Cut off to a simple base case. Recursing down to size 1 spends most calls on trivial work. Switching to insertion sort below a couple of dozen elements is a standard, measurable win.
• Allocate once. Slicing creates new lists at every level, O(n log n) allocation in total. Pass indices and reuse one buffer.
• Skip work you can detect. If the halves are already in order, the merge is unnecessary; this makes nearly sorted input close to linear.
• Bound the depth. CPython's default recursion limit is 1,000 frames, and native stacks are finite. Recurse on the smaller side and loop on the larger (the trick quicksort implementations use) so the depth is O(log n) whatever the input.

Divide and conquer is also cache-friendly without trying: once a sub-problem fits in cache, all of its recursive work runs from cache. The same blocking idea, made explicit, is how a GPU matrix multiply keeps tiles in shared memory.

Parallel divide and conquer

Independent sub-problems can run at the same time, which makes divide and conquer the natural shape for parallel code. Work T₁ is the total operations, the time on one core. Span T_inf is the longest chain of dependent steps, the time with unlimited cores. A work-stealing scheduler runs in about T₁/P + T_inf on P cores. Summing by halving has work Theta(n) and span Theta(log n), so it parallelises almost perfectly; mergesort with a sequential merge has span Theta(n), capping its speed-up at about log n.

import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveTask;

final class SumTask extends RecursiveTask<Long> {
    private static final int GRAIN = 10_000;   // below this, splitting costs more than it saves
    private final long[] a; private final int lo, hi;

    SumTask(long[] a, int lo, int hi) { this.a = a; this.lo = lo; this.hi = hi; }

    @Override protected Long compute() {
        if (hi - lo <= GRAIN) {                  // base case: plain loop, no task objects
            long s = 0;
            for (int i = lo; i < hi; i++) s += a[i];
            return s;
        }
        int mid = (lo + hi) >>> 1;               // unsigned shift avoids int overflow
        SumTask left = new SumTask(a, lo, mid);
        left.fork();                             // left half becomes stealable work
        long right = new SumTask(a, mid, hi).compute();   // this thread keeps the right half
        return right + left.join();
    }
}

long total = ForkJoinPool.commonPool().invoke(new SumTask(data, 0, data.length));

In Java's fork/join framework each worker keeps a deque of tasks and idle workers steal from the other end, so large chunks near the root migrate to idle cores. The grain size is the parallel base-case cutoff: too small and task overhead dominates, too large and cores idle at the end. Keep blocking I/O out of these tasks, since the common pool is sized to the number of cores.

Failure modes and trade-offs

Divide and conquer is not always the right shape. When sub-problems overlap, use dynamic programming; when one locally optimal choice is provably safe, greedy is simpler; and a bottom-up iterative version (merging runs of width 1, 2, 4 and so on) often has the same bound with no recursion at all. State the bound in Big-O terms first, then decide whether the recursion earns its overhead.

What to do next

1. Take one recursive function from your own code, write its recurrence (a, b and f(n)), and check the bound with a recursion tree before trusting it.
2. Implement counting inversions and test it against the quadratic version on random arrays.
3. Add a base-case cutoff to a mergesort and benchmark cutoffs from 8 to 64.
4. Feed your quicksort sorted input and many duplicate keys, measure depth and time, and fix pivot selection until both stay logarithmic and n log n.
5. Parallelise an array reduction with fork/join, vary the grain size by factors of ten, and plot speed-up against core count.
6. When a recursion is slow, check for overlapping sub-problems first.