Divide and conquer

What this chapter covers

Merge sort, quicksort, and binary search were all the same idea in different clothes: break a problem into smaller versions of itself, solve those, and combine. That idea is divide and conquer, and this chapter names it, studies what makes it fast, and gives the tool for analyzing it — the recursion tree and the Master Theorem. The vehicle is a problem where the obvious method is quadratic and a clever divide makes it subquadratic: multiplying large numbers. Grade-school multiplication is O(n²); Karatsuba's 1960 algorithm splits each number in half and — through an algebraic trick that turns four half-size multiplications into three — achieves O(n^1.585). That single change, four subproblems to three, is a perfect lesson in the paradigm: the combine step, not the division, decides a divide-and-conquer's complexity. This chapter builds Karatsuba, races it against schoolbook multiplication, and animates the recursion tree that explains exactly why three beats four.

A bit of history

Divide and conquer is old — binary search appears in the historical record centuries before computers, and John von Neumann described merge sort in 1945 — but the story that best captures the paradigm's power is Karatsuba's. In 1960 the 23-year-old Anatoly Karatsuba attended a seminar where Andrey Kolmogorov, one of the great mathematicians of the century, conjectured that multiplying two n-digit numbers required Ω(n²) operations — that grade-school multiplication was essentially optimal. Within a week Karatsuba disproved him, finding the three-multiplication trick that breaks the quadratic barrier. Kolmogorov was so struck that he wrote up the result himself (initially crediting Karatsuba almost as an afterthought). It was the first sign that fast multiplication was possible, and it opened a line of research that led to the FFT-based methods (Schönhage-Strassen, and in 2019 an O(n log n) algorithm) used to multiply the huge numbers in cryptography today. The lesson landed permanently: "obvious" quadratic algorithms are often not optimal, and a clever divide can beat them.

The intuition

Divide and conquer has three steps. Divide the problem into subproblems that are smaller instances of the same problem. Conquer them by recursion (until they're small enough to solve directly). Combine the subproblems' answers into the answer for the whole. Merge sort divides an array in half, recursively sorts each half, and combines by merging. Binary search divides the search interval in half and recurses into just one side (the combine is trivial). The paradigm's power is that a problem of size n is reduced to a few problems of size n/2, and repeating that collapses n toward 1 in only log n levels.

Karatsuba shows how much the combine matters. To multiply two n-digit numbers, split each into high and low halves: x = x_hi·B + x_lo and y = y_hi·B + y_lo, where B is 10 to the half-length. The product expands to x_hi·y_hi·B² + (x_hi·y_lo + x_lo·y_hi)·B + x_lo·y_lo — which naively needs four half-size multiplications (x_hi·y_hi, x_hi·y_lo, x_lo·y_hi, x_lo·y_lo). Four subproblems of half size gives the recurrence T(n) = 4T(n/2) + O(n), which works out to O(n²) — no improvement. Karatsuba's insight is that the middle term doesn't need two of those products: x_hi·y_lo + x_lo·y_hi equals (x_hi + x_lo)(y_hi + y_lo) − x_hi·y_hi − x_lo·y_lo, and the two subtracted products are ones you're already computing. So three half-size multiplications suffice — x_hi·y_hi, x_lo·y_lo, and the sum product — giving T(n) = 3T(n/2) + O(n) = O(n^log₂3) = O(n^1.585). The division is identical; only the combine changed, and that changed the complexity.

Complexity: how it scales

The recurrence T(n) = a·T(n/b) + f(n) is read by the Master Theorem, which compares the work at the leaves of the recursion tree, n^(log_b a), against the work f(n) done dividing and combining. For merge sort, a=2, b=2, f(n)=n: leaf work is n^(log₂2) = n, equal to f(n), giving O(n log n). For Karatsuba, a=3, b=2, f(n)=O(n): leaf work is n^(log₂3) = n^1.585, which dominates f(n), giving O(n^1.585). For binary search, a=1, b=2, f(n)=O(1): O(log n). The paradigm's cost is entirely in that three-way comparison. The face-off shows it empirically — Karatsuba against schoolbook as the numbers grow:

On a log-log plot, a power law is a straight line whose slope is the exponent, and schoolbook's line is steeper (slope ≈ 2) than Karatsuba's (slope ≈ 1.585) — the algorithms diverge as the numbers grow. At 512 digits Karatsuba was about 2.3 times faster, and the gap widens with size, exactly as the exponents predict. Notice, though, that at small sizes the two are close and schoolbook can even win: Karatsuba's recursion has overhead (the additions, the recursive calls) that only pays off once n is large enough for the better exponent to dominate. That's why real implementations, including CPython's integer multiply, use schoolbook for small numbers and switch to Karatsuba past a threshold — a recurring divide-and-conquer pattern, cut over to the naive method at the base case where it's actually faster.

What it's good at, what it isn't

Divide and conquer is the right approach when a problem decomposes into independent subproblems of the same kind whose answers combine cleanly — sorting, searching, fast arithmetic (Karatsuba, FFT multiplication and its use in signal processing), computational geometry (closest pair of points, convex hull), matrix multiplication (Strassen's algorithm, another "fewer subproblems" trick, 7 instead of 8), and many others. It's also the natural source of parallel algorithms: independent subproblems run on separate cores, and the recursion tree is a parallelism map. And it often turns an obvious quadratic or exponential method into something much faster, as Karatsuba did.

Where it's the wrong tool is problems whose subproblems overlap — where the same sub-instance recurs many times — because plain divide and conquer re-solves them redundantly, sometimes exponentially so (naive recursive Fibonacci is the cautionary tale). That's exactly the situation dynamic programming (two chapters ahead) fixes by remembering subproblem answers. Divide and conquer also carries recursion overhead that can make it slower than a simple loop on small inputs — hence the base-case cutoff — and it needs a combine step that's cheaper than solving from scratch, or there's no win. When subproblems are independent and the combine is cheap, it shines; when they overlap or the combine is costly, look elsewhere.

The data, or the inputs

The face-off multiplies pairs of random numbers of growing size, timing Karatsuba against a schoolbook O(n²) multiplier (both in Python, so the comparison is of the algorithms, not the language). Correctness is checked on thousands of random pairs against Python's built-in multiply — the trusted reference — plus some 400-digit cases for Karatsuba. The animation draws Karatsuba's recursion tree for an 8-digit multiply, revealing it level by level and annotating the work at each: one problem of size 8, then 3 of size 4, then 9 of size 2, then 27 single-digit leaves — the per-level work growing 8, 12, 18, 27, so the leaves dominate.

Build it, one function at a time

Karatsuba — the three-multiplication divide and conquer:

def karatsuba(x, y):
    """Multiply two non-negative integers with three half-size multiplications instead of four.
    Split x = hi_x·B + lo_x and y = hi_y·B + lo_y at the midpoint B = 10^m. The product is
    hi_x·hi_y·B^2 + (hi_x·lo_y + lo_x·hi_y)·B + lo_x·lo_y. Karatsuba computes the middle term as
    (hi_x+lo_x)(hi_y+lo_y) − hi_x·hi_y − lo_x·lo_y, so only THREE products are recursed on:
    z2=hi·hi, z0=lo·lo, and z1=(sum)(sum). T(n)=3T(n/2)+O(n) = O(n^1.585)."""
    if x < 10 or y < 10:                         # base case: single-digit multiply is direct
        return x * y
    m = max(len(str(x)), len(str(y))) // 2       # split near the middle
    B = 10 ** m
    hi_x, lo_x = divmod(x, B)
    hi_y, lo_y = divmod(y, B)
    z2 = karatsuba(hi_x, hi_y)                    # high·high
    z0 = karatsuba(lo_x, lo_y)                    # low·low
    z1 = karatsuba(hi_x + lo_x, hi_y + lo_y) - z2 - z0   # the cross terms, from ONE more product
    return z2 * B * B + z1 * B + z0

And the recursion-tree breakdown the Master Theorem reads:

def karatsuba_subproblems(n_digits, threshold=1):
    """How many single-multiplication leaves Karatsuba's recursion tree has for an n-digit input
    (each level triples the subproblem count while halving the size). Returns the per-level
    (count, size) breakdown — the shape the Master Theorem analyzes: work per level is
    count·size = n·(3/2)^level, a geometric series dominated by the leaves → O(n^log2(3))."""
    levels = []
    count, size = 1, n_digits
    while size > threshold:
        levels.append({"level": len(levels), "subproblems": count, "size": size,
                       "work": count * size})
        count *= 3
        size = (size + 1) // 2
    levels.append({"level": len(levels), "subproblems": count, "size": size, "work": count * size})
    return levels

Watch it work

Here's Karatsuba's recursion tree for multiplying two 8-digit numbers, revealed one level at a time. The root (top) is the single size-8 problem. It branches into three size-4 subproblems — three, not four, which is the whole trick — each of which branches into three size-2 problems, and those into three single-digit leaves. Watch the annotation as each level lights up: level 0 does 8 units of work, level 1 does 12, level 2 does 18, level 3 does 27. The work grows by half again at each level down, so the bottom — the 27 single-digit leaves — dominates the total. That's the Master Theorem's "leaves dominate" case made visual, and 27 ≈ 8^1.585 is exactly the n^log₂3 that gives Karatsuba its subquadratic complexity. Had each node branched four ways instead of three, the leaves would number 64 = 8², and you'd be back to schoolbook:

The complete code

The from-scratch tab is Karatsuba with its recurrence breakdown; the library tab is the schoolbook O(n²) multiplier it's raced against, with a note that Python's own int multiply switches to Karatsuba past ~70 digits. Flip between them.

"""Divide and conquer — the paradigm that generated half the algorithms in this book. Break
a problem into smaller instances of the same problem, solve those recursively, and combine
their answers. Merge sort, quicksort, and binary search were all divide-and-conquer; this
chapter names the pattern and studies what makes it pay off, through a problem where the naive
method is quadratic and a clever DIVIDE makes it subquadratic: multiplying large numbers.

Multiplying two n-digit numbers the way you learned in school is O(n^2) — every digit of one
times every digit of the other. In 1960 Anatoly Karatsuba found something better. Split each
number into high and low halves; the product then needs four half-size multiplications
(high·high, high·low, low·high, low·low). That's still O(n^2) — four subproblems of half size
is no win. Karatsuba's trick is algebraic: those four products can be recovered from just
THREE half-size multiplications, because the cross terms high·low + low·high can be computed
from one extra product minus the two you already have. Three instead of four changes the
recurrence from T(n)=4T(n/2) (=n^2) to T(n)=3T(n/2), which is O(n^1.585) — subquadratic, and a
textbook lesson in how the COMBINE step decides a divide-and-conquer's complexity.
"""


# region: karatsuba
def karatsuba(x, y):
    """Multiply two non-negative integers with three half-size multiplications instead of four.
    Split x = hi_x·B + lo_x and y = hi_y·B + lo_y at the midpoint B = 10^m. The product is
    hi_x·hi_y·B^2 + (hi_x·lo_y + lo_x·hi_y)·B + lo_x·lo_y. Karatsuba computes the middle term as
    (hi_x+lo_x)(hi_y+lo_y) − hi_x·hi_y − lo_x·lo_y, so only THREE products are recursed on:
    z2=hi·hi, z0=lo·lo, and z1=(sum)(sum). T(n)=3T(n/2)+O(n) = O(n^1.585)."""
    if x < 10 or y < 10:                         # base case: single-digit multiply is direct
        return x * y
    m = max(len(str(x)), len(str(y))) // 2       # split near the middle
    B = 10 ** m
    hi_x, lo_x = divmod(x, B)
    hi_y, lo_y = divmod(y, B)
    z2 = karatsuba(hi_x, hi_y)                    # high·high
    z0 = karatsuba(lo_x, lo_y)                    # low·low
    z1 = karatsuba(hi_x + lo_x, hi_y + lo_y) - z2 - z0   # the cross terms, from ONE more product
    return z2 * B * B + z1 * B + z0
# endregion


# region: recurrence
def karatsuba_subproblems(n_digits, threshold=1):
    """How many single-multiplication leaves Karatsuba's recursion tree has for an n-digit input
    (each level triples the subproblem count while halving the size). Returns the per-level
    (count, size) breakdown — the shape the Master Theorem analyzes: work per level is
    count·size = n·(3/2)^level, a geometric series dominated by the leaves → O(n^log2(3))."""
    levels = []
    count, size = 1, n_digits
    while size > threshold:
        levels.append({"level": len(levels), "subproblems": count, "size": size,
                       "work": count * size})
        count *= 3
        size = (size + 1) // 2
    levels.append({"level": len(levels), "subproblems": count, "size": size, "work": count * size})
    return levels
# endregion

"""The library counterpart and the contrast. Python's built-in `int` multiplication IS a
divide-and-conquer algorithm: CPython switches from schoolbook to Karatsuba automatically once
the operands exceed ~70 digits, so `x * y` on big integers is already subquadratic. That built-in
is the correctness reference (`karatsuba(x, y)` must equal `x * y`).

The contrast that makes Karatsuba's point is SCHOOLBOOK multiplication — the O(n^2) grade-school
algorithm, four half-products' worth of digit-by-digit work. `schoolbook` below implements it on
digit lists so the trace generator can time quadratic against subquadratic as the numbers grow.
"""


# region: schoolbook
def schoolbook(x, y):
    """Grade-school multiplication: every digit of x times every digit of y, summed with carries.
    O(n^2) digit multiplications. The quadratic baseline Karatsuba's three-way split beats."""
    dx = [int(c) for c in str(x)][::-1]           # least-significant digit first
    dy = [int(c) for c in str(y)][::-1]
    acc = [0] * (len(dx) + len(dy))
    for i, a in enumerate(dx):
        for j, b in enumerate(dy):
            acc[i + j] += a * b                    # the O(n^2) core: every pair of digits
    # resolve carries
    carry = 0
    for i in range(len(acc)):
        acc[i] += carry
        acc[i], carry = acc[i] % 10, acc[i] // 10
    return int("".join(str(d) for d in acc[::-1]).lstrip("0") or "0")
# endregion

Scratch vs library

Karatsuba against schoolbook is the paradigm's thesis in miniature: same problem, same way of dividing, but a cleverer combine drops the complexity from n² to n^1.585 — and the recursion tree, not intuition, is what tells you so. That's the deliverable of this chapter, a way to think rather than a single algorithm. Every divide-and-conquer you've met or will meet — merge sort, quicksort, binary search, Strassen's matrix multiply, the FFT, closest-pair — is analyzed by writing its recurrence and reading the Master Theorem, and designed by asking "can I reduce the number of subproblems, or make the combine cheaper?" It's telling that Python's own integer multiplication is exactly this: schoolbook below a threshold, Karatsuba above it, the classic base-case cutover. Building Karatsuba yourself is what makes the abstract recurrence T(n) = 3T(n/2) + O(n) into a tree you've watched fill in, and the "three beats four" insight into something you've measured.

Where you'll actually meet it

Divide and conquer is everywhere in computing's foundations. Sorting (merge sort, quicksort) and searching (binary search) are its most-run instances. Big-number arithmetic in cryptography and computer algebra uses Karatsuba and its FFT-based successors (Python, Java's BigInteger, and GMP all switch to Karatsuba for large operands). Signal and image processing runs on the FFT, the most famous divide-and-conquer of all. Matrix computations use Strassen's algorithm and its descendants. Computational geometry solves closest-pair and convex-hull by dividing space. Parallel and distributed systems use it as the template for splitting work across cores and machines (MapReduce is divide-and-conquer at datacenter scale). And it's the mental model for recursion itself — whenever a problem's answer is built from the answers to smaller versions of it, you're thinking divide and conquer.

Takeaways

Divide and conquer solves a problem by splitting it into smaller instances of itself, recursing, and combining, with its cost captured by the recurrence T(n) = a·T(n/b) + f(n) and read off by the Master Theorem's three cases (leaves dominate, balanced, root dominates). Karatsuba multiplication makes the paradigm's central lesson concrete: dividing each number in half but combining with three half-size multiplications instead of four drops the complexity from O(n²) to O(n^1.585) — the combine, not the division, sets the exponent. The recursion tree, with work growing toward the leaves, is why.

The next chapters cover the other great algorithm-design paradigms. Greedy algorithms (next) build a solution by making the locally best choice at each step and — when a problem has the right structure — reaching a global optimum, as Huffman coding, Dijkstra, and the MST algorithms already did. Then dynamic programming tackles the overlapping-subproblems case divide and conquer can't, by remembering answers instead of recomputing them.