Divide and Conquer

Split the problem into smaller copies of itself, solve those and combine the answers. Binary search, merge sort, quicksort and the multiplication inside Python's big integers all work this way. The technique is old and ordinary, and its value is that the cost of the result can be read straight off a picture of the recursion: how many pieces per level, how large they are, and how much work it takes to put them back together.

No equation needs solving. Chapters 7 and 8 already used this shape inside particular algorithms; this topic names it, shows the three costs it can produce, and shows where it fails, which is when the split comes out uneven or the pieces turn out to share work.

Split, Solve, Combine

Every divide-and-conquer algorithm has the same three steps plus a base case. Split the input into smaller pieces. Solve each piece with the same procedure. Combine the pieces' answers into an answer for the whole. The base case is a piece small enough to solve directly, such as a list of one item, which is already sorted.

The figure shows one step of merge sort on eight numbers. The split cuts 7, 2, 9, 4, 3, 8, 6, 1 into two halves. Each half is sorted by the same procedure, giving 2, 4, 7, 9 and 1, 3, 6, 8. The combine step merges them, taking the smaller front item each time, and on this input it needs 7 comparisons to produce all eight numbers in order.

Where the effort sits differs between algorithms. Merge sort does its work in the combine, and its split is free. Quicksort does its work in the split, partitioning around a pivot, and its combine is free. Binary search from Chapter 7 does almost no work anywhere: it throws half the problem away at every step and never combines anything.

Why Halving Gives log n

A problem cut in half at every step is down to one item after log n steps, the logarithm to base 2. For a million items that is 20 steps; for a billion it is 30. Doubling the input adds one step. That count is the depth of every balanced divide-and-conquer tree, and it is why a log n appears wherever halving does, from binary search to the balanced trees of Chapter 6.

Reading the Cost off the Tree

The method is always the same: add up the work on each level of the recursion, then count the levels. Three shapes cover most algorithms, and the figure draws all three for eight items with each level's total work written on the right.

On the left, the algorithm halves the problem, keeps one half and does constant work: 1 per level over 4 levels, a total of 4. That is binary search, O(log n). In the middle, it halves, keeps both halves and does linear work to combine them: 8 on every level over 4 levels, a total of 32. That is merge sort, O(n log n). On the right, it halves, keeps both halves and combines in constant time: 1, 2, 4 and 8, a total of 15. The bottom level alone holds more than half the work, so the leaves dominate and the whole is O(n), the cost of touching every item once.

When Splitting Beats the Obvious Method

Multiplying two n-digit numbers the schoolbook way costs n² digit products: every digit of one against every digit of the other. Split each number into a high half and a low half and the product needs four half-size multiplications, which saves nothing. Karatsuba's trick computes the same product from three half-size multiplications plus some additions. Three branches per level over log n levels comes to about n to the power 1.58 instead of n². CPython switches to Karatsuba once both numbers are longer than 70 of its internal 30-bit digits, about 2,100 bits or 630 decimal digits.

Raising a number to a large power is the second classic. Multiplying x by itself 65,536 times gives x to the 65,537th. Halving the exponent instead gets there in 17 multiplications, because 65,537 is 2 to the 16th plus 1: sixteen squarings and one extra multiplication. That is the core step of RSA encryption, which Chapter 14 returns to, and it is the difference between a key operation that finishes and one that does not.

def power(x, n):
    if n == 1:
        return x
    half = power(x, n // 2)        # solve the half-size problem once
    square = half * half              # combine: one multiplication
    return square * x if n % 2 else square

The function above solves the problem for half the exponent once, squares the result, and multiplies by x one more time when the exponent is odd. Each level of recursion halves n, so there are about log n levels with one or two multiplications each. Counted on CPython 3.15 with an exponent of 65,537, it performs exactly 17 multiplications and returns the same number as the built-in power operator.

When the Split Is Uneven

Depth decides cost. Halving gives log n levels. Peeling off one item per step gives n levels, and linear work on each of n levels turns n log n into n². That is quicksort with a bad pivot from Chapter 7: on already sorted input a first-element pivot splits n items into nothing and n − 1, again and again.

The same unevenness exhausts the call stack from Chapter 3. Recursion n levels deep on 10,000 items asks CPython for 10,000 frames, and the default limit is 1,000, so the call raises RecursionError long before memory runs out. Careful implementations recurse only into the smaller part and loop over the larger one. The smaller part is at most half the input, so the depth stays at log n, about 20 for a million items, whatever the input looks like.

What Recursion Costs in Practice

A function call has a fixed overhead that dwarfs the work at the leaves. On CPython 3.15 even an empty function call measures in the tens of nanoseconds, and the work it wraps at a leaf of a sort is a comparison or two. So real implementations stop dividing at a few dozen items and finish with a simple method; every library sort in Chapter 7 switches to insertion sort for short runs for this reason.

The same shape pays off on parallel hardware. Independent halves are the natural unit of work for several cores, the subject of Chapters 3 and 11: split the input, hand each half to a core, combine at the end. On one core, splitting halves nothing, because the total work is unchanged. The same split-and-combine shape spread over many machines is where this book stops and a System Design course would begin.