Divide & Conquer Beyond Sorting

In short: divide and conquer isn't only for sorting. Split the input, solve each half recursively, then combine the two answers — and the combine step is where the whole technique either pays off or doesn't. It wins when the combine is cheap (two half-size streak searches plus one linear crossing sweep) or when a clever combine needs fewer recursive calls than the obvious split (Karatsuba's three multiplies instead of four). Write the recurrence before you write the code: if the combine costs as much as solving the problem directly, or the halves overlap, divide and conquer won't help.

An 8-day array split at the middle: the best streak can live entirely left, entirely right, or cross the middle as a left tail plus a right head, 3 + 8 = 11

Merge sort taught you the pattern: divide the input, conquer each piece recursively, combine the answers. Lesson 1 gave you the tool to price it: $T(n) = a\,T(n/b) + f(n)$ . This lesson uses the pattern on problems that have nothing to do with putting things in order, and uses the recurrence to predict, before you write a line, whether splitting will pay.

The rule of thumb from the master theorem: divide and conquer wins when the combine is cheaper than solving the whole problem directly, or when you can get away with fewer recursive calls than the obvious split needs.

Fewer calls: multiplying big numbers

Tunebox's royalty ledger multiplies very large integers. The schoolbook method multiplies every digit of one number by every digit of the other: n² single-digit multiplications for two n-digit numbers.

Divide and conquer splits each number into a high half and a low half, $x = x_h \cdot 10^m + x_l$ , and expands the product:

x \cdot y = x_h y_h \cdot 10^{2m} + (x_h y_l + x_l y_h) \cdot 10^m + x_l y_l

That is four half-size multiplications: $T(n) = 4T(n/2) + n$ , which is still $\Theta(n^2)$ . No gain. The trick, found by Karatsuba, is that the middle term can be had from one multiplication, reusing the other two:

x_h y_l + x_l y_h = (x_h + x_l)(y_h + y_l) - x_h y_h - x_l y_l

Step through it on two 8-digit numbers. The array is the digits of x then y:

watch it move · array

Three half-size multiplies instead of four. One saved multiply per level compounds into a smaller exponent.

Split both numbers at m = 4 digits. The high halves are 1234 and 8765. 16 cells.

1 / 7

The recurrence becomes $T(n) = 3T(n/2) + n$ . Three calls on halves, the leaves dominate, and the cost is $n^{\log_2 3} \approx n^{1.585}$ . Count it:

python

At 64 digits it uses under a third of the schoolbook count. The sums $x_h + x_l$ can carry into an extra digit, which inflates the small cases, but look at the ratios: each doubling of the digits multiplies Karatsuba's count by about 3 and the schoolbook's by 4.

❓ Cross-question — "Does Python do this?" Yes. CPython's integer multiply switches to Karatsuba once both numbers are several hundred digits long. Below that, the schoolbook loop's lower overhead wins. The numbers for that trade-off come next.

Karatsuba does more additions and bookkeeping per level than the schoolbook loop, so its real cost is roughly $c \cdot n^{1.585}$ for some overhead c against $n^2$ . At 1,000 digits that's c × 56,870 against 1,000,000:

overhead `c`	Karatsuba	schoolbook	cheaper
10	568,706	1,000,000	Karatsuba
17	966,800	1,000,000	Karatsuba
18	1,023,670	1,000,000	schoolbook
30	1,706,117	1,000,000	schoolbook

Karatsuba wins only while c is below about 17.6. A better exponent always wins eventually, but the constant decides where "eventually" starts, which is why real libraries switch methods at a threshold.

Cheaper combine: a track's best streak

Tunebox keeps each track's daily change in listeners: +3 means three more listeners than the day before, -5 means five fewer. The label wants the best streak, the run of consecutive days with the largest total gain.

Checking every start and end is $O(n^2)$ runs. Divide and conquer splits the days in half. The best streak is in one of three places:

entirely in the left half, which the left recursive call finds;
entirely in the right half, which the right call finds;
crossing the middle: it ends somewhere in the left half's tail and starts somewhere in the right half's head.

The crossing case is the combine step, and it is linear: grow a run leftwards from the middle keeping the best sum, grow one rightwards the same way, and add the two. So $T(n) = 2T(n/2) + n$ , the merge sort recurrence, $O(n \log n)$ .

Here is the crossing case on its own. Step through the left sweep:

step through it

1d = [3, -5, 4, -1, 2, 6, -7, 2]

2mid = 4

3total, best_left = 0, None

4for i in range(mid - 1, -1, -1):

5 total += d[i]

6 if best_left is None or total > best_left:

7 best_left = total

8print(best_left)

Before running the next one, work out what the crossing run is worth:

What does this print?

d = [3, -5, 4, -1, 2, 6, -7, 2]
mid = 4

total, best_left = 0, None
for i in range(mid - 1, -1, -1):
    total += d[i]
    best_left = total if best_left is None else max(best_left, total)

total, best_right = 0, None
for j in range(mid, len(d)):
    total += d[j]
    best_right = total if best_right is None else max(best_right, total)

print(best_left + best_right)

Now watch your own divide and conquer run on all eight days. Each frame after a split shows the range being combined, the middle pointer, and the best crossing run in green. Change the deltas, or try an all-negative history:

your code, drawn · array

Your best-streak search. The crossing run is the only new work each call does, and it is linear in the range.

Leave out the crossing case and the algorithm is still recursive, still fast, and wrong:

broken — fix it

This should print 11, the streak 4, -1, 2, 6. It prints 6: with no crossing case, the only runs it can ever return are single days.

Halving the exponent: fast power

Divide and conquer also works on a single number. To compute $x^n$ , don't multiply n times. Split the exponent: $x^n = (x^{n/2})^2$ when n is even, and $x \cdot x^{n-1}$ when it is odd. One call on half the problem, constant combine: $T(n) = T(n/2) + 1$ , $O(\log n)$ .

What does this print?

mults = 0

def power(x, n):
    global mults
    if n == 0:
        return 1
    if n == 1:
        return x
    if n % 2 == 0:
        half = power(x, n // 2)
        mults += 1
        return half * half
    mults += 1
    return x * power(x, n - 1)

power(3, 1000)
print(mults)

The same trick works on anything you can multiply associatively, including matrices. A graph's adjacency matrix raised to the power k counts the walks of exactly k hops between every pair of nodes, and fast power computes it with $O(\log k)$ matrix products. That is the capstone exercise.

When dividing does not help

Divide and conquer is not free. Before reaching for it, write the recurrence:

The combine is as expensive as the whole problem. Splitting a list to find its maximum gives $T(n) = 2T(n/2) + 1$ , which is $O(n)$ : no better than a loop, with recursion overhead on top.
The pieces overlap. Naive Fibonacci splits fib(n) into fib(n-1) and fib(n-2), which share almost everything. When subproblems repeat, you need a memo, which is dynamic programming from section 6, not divide and conquer.
A simpler scan exists. The best streak has a one-pass $O(n)$ solution: keep the best run ending at today, and either extend it or start fresh. Divide and conquer is worth knowing here because its shape generalises to cases the scan cannot handle, like combining streak summaries from many servers.

python

Idioms & real-world patterns

Pass bounds, not slices

Every recursive function in this lesson takes lo and hi rather than slicing. Slices copy, and a copy in the combine step can turn a +1 into a +n and change the whole recurrence.

`pow(x, n, mod)` is fast power

Python's three-argument pow does exactly the squaring trick, keeping every intermediate value below mod. pow(3, 10**18, 1_000_000_007) returns instantly.

⚡ Advanced — the same idea, other places

The fast Fourier transform multiplies polynomials in $O(n \log n)$ by splitting into even and odd coefficients. Strassen's method multiplies matrices with 7 half-size products instead of 8, giving $n^{\log_2 7} \approx n^{2.81}$ . In each case, the win is one fewer recursive call, compounded over log n levels.

Quick practice

What does this print?

mults = 0

def power(x, n):
    global mults
    if n == 0:
        return 1
    if n == 1:
        return x
    if n % 2 == 0:
        half = power(x, n // 2)
        mults += 1
        return half * half
    mults += 1
    return x * power(x, n - 1)

print(power(2, 13), mults)

broken — fix it

2⁵ is 32. This prints 1, because halving odd exponents with no "and multiply by x once more" case throws away a factor of x at every odd level.

🎯 Your turn

Write best_streak(deltas): the largest total of any run of one or more consecutive days. deltas is never empty. Use divide and conquer: left half, right half, and the run that crosses the middle.

best_streak([3, -5, 4, -1, 2, 6, -7, 2]) → 11
best_streak([-4, -2, -9]) → -2, a streak must contain at least one day

Hint — write a helper on lo and hi. Its base case is one day. Its combine is the best left tail plus the best right head, as in the trace above.

Then press ▶ Run, tap the Live App try chips, and hit ✓ Check.

Divide & Conquer Beyond Sorting

Divide & Conquer Beyond Sorting

Fewer calls: multiplying big numbers

Cheaper combine: a track's best streak

Halving the exponent: fast power

When dividing does not help

Idioms & real-world patterns

Pass bounds, not slices

pow(x, n, mod) is fast power

⚡ Advanced — the same idea, other places

Quick practice

🎯 Your turn

Practice — level up

`pow(x, n, mod)` is fast power