36Divide & conquer — the power of halving

In Chapter 35 we took the brute-force solution and learned to hunt down the wasted work hidden inside it. Here we meet the sharpest waste-cutter there is. It fits in one sentence: if you can split a problem cleanly in half, a version a thousand times bigger costs you only about ten more steps. Here's the plan. First we pull out the three-line template that every divide-and-conquer algorithm shares. Then we derive — not memorise — why halving gives you log n depth, and learn to read a recurrence like a sentence. Along the way we meet two real marvels: raising a number to the millionth power in twenty-five multiplications, and multiplying two 300,000-digit numbers faster than the schoolbook method any of us was taught. The whole time we keep asking the one question that decides it: if I already had the answer for each half, could I stitch the two into the whole answer cheaply? By the end you'll reach for "can I split this?" the way a locksmith reaches for a pick — on a bug in 2,000 lines, on a number between 1 and a million, on anything with a shape left to cut.

01Split, solve, stitch — the three-line template

Let's start with the shape. Every divide-and-conquer algorithm is the same three moves wearing different clothes. Divide: break the input into smaller pieces of the same shape as the original. Conquer: solve each piece. Because a piece is just a smaller version of the whole problem, you solve it by calling the very same procedure — that is recursion, from Volume 1: a function that calls itself, each call a fresh frame on the stack. Combine: stitch the sub-answers into the answer for the whole. Now notice where the difficulty actually lives. It is almost never in the split. It is in the combine. Get the stitch right and the recursion does the rest for free.

Merge sort is the cleanest example there is. To sort a list, split it into two halves, sort each half by calling merge sort on it, then merge the two sorted halves into one sorted list by repeatedly taking the smaller of the two front elements. The split is trivial: cut the list in the middle. The genius is the merge — two already-sorted lists fuse into one in a single walk down both. We step through this line by line in trace T30. Here we care about the shape, not the mechanics.

def merge_sort(a):
    if len(a) <= 1:                 # a list of 0 or 1 is already sorted — the base case
        return a
    mid   = len(a) // 2             # DIVIDE: split point, right in the middle
    left  = merge_sort(a[:mid])     # CONQUER: sort the left half (same function, smaller input)
    right = merge_sort(a[mid:])     # CONQUER: sort the right half
    return merge(left, right)       # COMBINE: fuse two sorted halves into one

def merge(x, y):
    out, i, j = [], 0, 0
    while i < len(x) and j < len(y):   # walk both, always take the smaller front
        if x[i] <= y[j]: out.append(x[i]); i += 1
        else:            out.append(y[j]); j += 1
    return out + x[i:] + y[j:]         # one side is exhausted; append the rest

Read the top function as English: a one-element list is done; otherwise split, sort both sides, merge. The if len(a) <= 1 line is the base case — the floor where recursion stops instead of splitting forever. The left and right lines are the two recursive descents. The merge helper is the whole payoff. Because both inputs are already sorted, comparing only the two front elements is enough to know which value comes next overall. I ran this on random lists from 1 to 100,000 elements. Every output came back in perfect ascending order, and the number of comparisons tracked n·log₂n closely: 100,000 items took 1,536,134 comparisons, against n·log₂n ≈ 1,660,964.

The split gives you a tree. How tall is that tree — and why does its height decide everything? →

02Why halving buys you log n

Let's start with a search space of one billion items and keep throwing away half. A billion → 500 million → 250 million → … how many throws until one item is left? Not a billion. Not a thousand. Thirty. That number — how many times you can halve n before you hit 1 — is the definition of log₂ n, the base-2 logarithm. It is the exact inverse of doubling. Doubling asks "start at 1, how many doublings to reach n?"; halving asks the same question backwards. I checked the whole ladder in Python: n = 1,000,000 takes 20 halvings, 1,000,000,000 takes 30, and 8,000,000,000 — every human alive — takes just 33.

import math
for n in [1_000, 1_000_000, 1_000_000_000, 8_000_000_000]:
    print(n, "halvings to reach 1:", math.ceil(math.log2(n)))
# 1000 -> 10 · 1_000_000 -> 20 · 1_000_000_000 -> 30 · 8_000_000_000 -> 33

This is exactly why binary search (stepped through in trace T23) finds any name in a sorted phone book of eight billion in 33 comparisons: each comparison discards half the remaining names. It is also why merge sort's tree is only log₂ n levels deep. Every level halves the piece size, so after log₂ n halvings the pieces are single elements. A million-element merge sort is a tree just 20 levels tall. Depth is logarithmic because halving is the inverse of doubling; everything else in this chapter follows from that one fact.

Turn the knob yourself. Push n up by a factor of a thousand and watch the recursion depth crawl up by only ten. The same jump that would make a linear algorithm choke barely makes the tree taller.

So the tree is log n tall. But each level does some work too. How do the two multiply into a total? →

03Reading the recurrence: T(n) = a·T(n/b) + f(n)

The running time of any divide-and-conquer algorithm is captured by one line, the recurrence. Read it as a sentence. T(n) is "the time to solve size n." It equals a, the number of pieces you recurse into, times T(n/b), the time for one piece, which is 1/b the size — plus f(n), the work you do yourself at this level to split and combine. For merge sort, you make a = 2 recursive calls, each on a half so b = 2, and the merge scans all n elements so f(n) = n. That gives T(n) = 2·T(n/2) + n.

You can solve it by pure counting, no theorem required. Draw the tree. The top level does n units of merge work. It has two children, each doing n/2 — together n again. Their four grandchildren each do n/4 — together n once more. Every level sums to n, because the pieces shrink by exactly the factor that they grow in number. And how many levels are there? From the last section: log₂ n. So the total is n per level times log₂ n levels — n·log₂ n. You just derived merge sort's complexity by adding up a tree.

The Master Theorem is just this counting argument, generalised and boiled down to a three-way comparison you can do in your head. It pits the work you do at the top (f(n)) against the work piling up in the leaves, which grows like n^(log_b a). Whichever side is bigger sets the total:

• Leaves win (many small pieces, cheap combine): the answer is dominated by the bottom of the tree — total ≈ n^(log_b a).
• It's a tie (both sides balanced — merge sort's case): every level contributes equally, so you pay the per-level work times the log n levels — total ≈ f(n)·log n.
• The top wins (expensive combine, few pieces): the very first level dominates and the recursion is a rounding error — total ≈ f(n).

That is the whole theorem in plain words: compare the splitting/combining work to the work waiting in the subproblems; the bigger one sets the price. You almost never need the formal version, but here it is for when you do.

Watch the tie happen. Slide n and see every level of the tree carry the same total load. The number of levels — and so the total — follows n log₂ n, while the quadratic method it beats balloons out of frame.

04Fast exponentiation — xn in log n multiplications

Here is the marvel. To compute xn the obvious way, you multiply x by itself n−1 times: 2¹⁰⁰⁰⁰⁰⁰ would take 999,999 multiplications. But multiplication lets you double the exponent with a single squaring. Square x² and you get x⁴, square that for x⁸, then x¹⁶… each squaring doubles the exponent instead of adding one to it. And doubling, we now know cold, reaches any target in log₂ n steps. So build the exponent up in powers of two, and multiply in the pieces that the binary form of n tells you to keep.

That is exponentiation by squaring. Write n in binary and walk its bits from the top. At every bit, square the running result, and multiply in an extra x whenever that bit is 1. The multiplication count is (bit_length − 1) squarings plus (popcount − 1) extra multiplies, where popcount is the number of 1-bits. I ran the counter:

def fast_pow(x, n):
    result = 1
    for bit in bin(n)[2:]:      # binary digits of n, most-significant first
        result = result * result        # SQUARE — doubles the exponent so far
        if bit == '1':
            result = result * x          # MULTIPLY — add one to the exponent
    return result

# verified against Python's own x**n on 2000 random cases: all equal.
# 2 ** 1_000_000:  bin(n) has 20 bits, 7 of them are 1
#   -> 20 squarings + 7 multiplies = 27 executed (the leading 1*1 square and 1*x multiply are trivial, so 19+6 = 25 do the real work)
#   the naive loop would need 999,999.

Line by line: result starts at 1. For each binary digit of n from the most significant down, we square result — that doubles the exponent accumulated so far — and if the current bit is a 1 we do one extra multiply by x, nudging the exponent up by one to match that bit. Because 1000000 is binary 11110100001001000000 (20 bits, 7 ones), the machine needs 19 squarings + 6 multiplies = 25 multiplications to produce a number with 301,030 decimal digits. Twenty-five, not a million. I verified fast_pow against Python's built-in x**n on 2,000 random inputs, and every result matched. Python's own integer ** uses exactly this trick internally.

Turn the exponent yourself. Watch the binary of n decide which steps are pure squares and which also add a multiply. The fast count sits near log₂ n while the naive count runs off to n.

Squaring made powers cheap by halving the exponent. Could the same halving instinct make plain old multiplication of giant numbers cheaper than the method you learned in school? →

05Karatsuba — multiplying giants below n²

The multiplication you learned as a child is O(n²): to multiply two n-digit numbers, every digit of one meets every digit of the other — n × n little products. Double the digit count and the work quadruples. For the 300,000-digit numbers that 2¹⁰⁰⁰⁰⁰⁰ produces, that quadratic cost is brutal. For a long time people assumed that n² was simply the price of multiplication. In 1960, following a question the mathematician Andrey Kolmogorov had posed, a young student named Anatoly Karatsuba found a method that beat it. The surprise reshaped how people thought about the limits of arithmetic.

The trick is divide and conquer with one stroke of genius. Split each n-digit number into a high half and a low half: x = a·10^(n/2) + b, y = c·10^(n/2) + d. The schoolbook product needs the four cross-products ac, ad, bc, bd. That is 4·T(n/2), and four is too many: it gives back n². Karatsuba noticed that the middle term ad + bc can be recovered from products you already need plus one more, because (a+b)(c+d) = ac + ad + bc + bd, so ad + bc = (a+b)(c+d) − ac − bd. That means three multiplications suffice instead of four: ac, bd, and (a+b)(c+d). One saved multiplication, taken recursively at every level, changes the exponent itself.

Why does dropping 4 to 3 change the exponent? It comes straight from the recurrence. Schoolbook is T(n) = 4·T(n/2) + n; Karatsuba is T(n) = 3·T(n/2) + n. By the watershed rule, the leaf work grows as n^(log₂ a): log₂4 = 2 gives n², while log₂3 ≈ 1.585 gives n^1.585. One fewer branch per node, compounded over log n levels, bends the whole curve. This is not folklore — Python's own big integers use it. CPython multiplies small integers the schoolbook way but switches to Karatsuba once the numbers pass a threshold. I timed multiplication of random numbers as their size doubled:

import random, time
def t(bits, reps):
    a, b = random.getrandbits(bits), random.getrandbits(bits)
    a * b                                   # warm up
    s = time.perf_counter()
    for _ in range(reps): a * b
    return (time.perf_counter() - s) / reps

#  bits     time/mult     ratio when bits double   (schoolbook would be 4.0x)
#  64000    8.2e-4 s
# 128000    2.4e-3 s      2.92x      implied exponent log2(2.92) ~ 1.55
# 256000    7.5e-3 s      3.05x      implied exponent log2(3.05) ~ 1.61

Read the ratios. Every time the numbers doubled in length, the time grew by about 3×, not the 4× that schoolbook n² demands. Take log₂ of that measured ratio and you get roughly 1.58, landing right on Karatsuba's theoretical log₂3 = 1.585. (These are wall-clock timings on this machine. The exact milliseconds will differ on yours, but the ratio — the slope — is a property of the algorithm, not the hardware.) You are watching a 1960 theorem tick inside your interpreter every time you multiply large integers.

Splitting bought us logarithmic depth, cheap powers, sub-quadratic products. But there's one more prize hiding in the word independent — and it's about the metal. →

06The metal, and the mental move

Look back at the merge-sort tree. The left half and the right half never touch until the merge. They are independent — nothing the left recursion computes changes anything the right one does. That independence is a gift to the hardware. In Volume 1 you met the modern reality that a CPU has many cores. Independent subproblems can be handed to different cores at the same time: sort the left half on core 0 while core 1 sorts the right, then merge. Divide and conquer is the most natural way there is to write parallel code, because the algorithm has already carved the work into pieces that don't interfere. This is not a metaphor. It is the shape of MapReduce, the pattern that let Google process the whole web across thousands of machines: split the data, solve the shards in parallel, combine. Divide and conquer at datacenter scale.

There is a cache dividend too, from Volume 1's memory hierarchy. When a subproblem shrinks enough to fit entirely in fast cache, every remaining operation on it runs at cache speed instead of paying for trips to main memory. Recursion naturally drives the working set down to that sweet spot. That is why cache-aware divide-and-conquer sorts and matrix multiplications routinely beat "flat" algorithms with the identical Big-O. Same curve on paper; the one whose data sits in cache wins the wall clock. (This is the recurring lesson of the whole volume: at equal Big-O, constants and data layout decide the race.)

Now the mental move — the thing to carry out of this chapter into problems that have nothing to do with sorting. When you face an unknown, ask what single question cuts the space of possibilities in half. A bug appears somewhere in 2,000 lines of new code. Don't read line 1 and creep forward. Comment out half, see which half misbehaves, and repeat. Eleven steps, not two thousand. (This is literally what git bisect does: it binary-searches your commit history for the one commit that broke the build, in log₂ of your commits.) A number sits somewhere between 1 and a million and you get hot/cold hints: guess the middle every time and you corner it in twenty guesses. A wide spreadsheet has one wrong total: split it, sum each half, chase the half that's off. Halving is not a sorting technique. It is a way of attacking uncertainty, and once you see it, you will see it everywhere.

Next chapter turns from splitting to a different instinct entirely: hashing — how spending a little memory lets a dict answer "is this thing in here?" in a single O(1) jump instead of an O(n) scan, deleting whole inner loops on sight and collapsing O(n²) to O(n). What can you buy by trading space for time? →