Divide and Conquer: Split, Solve, Combine

This lesson is in Level 3, Advanced. It assumes you can read a recursive function and that you have met merge sort and quick sort in Sorting Algorithms. Those two are only recapped here.

#Split, Solve, Combine

The exam-paper story fits. Divide: hand each person a pile. Conquer: each person counts a pile. Combine: add the counts. The combine step here is cheap, one addition per person. In other problems the combine step is where all the work hides, and that is why we will learn to measure it.

Here is the smallest possible example. It adds a list by splitting it into halves, and it counts how many calls it makes.

def sum_halves(items, lo, hi, counter):
    counter[0] += 1                      # count every call
    if hi - lo == 1:                     # base case: one value
        return items[lo]
    mid = (lo + hi) // 2
    left = sum_halves(items, lo, mid, counter)     # conquer the left half
    right = sum_halves(items, mid, hi, counter)    # conquer the right half
    return left + right                            # combine: one addition


for n in (1, 2, 8, 100, 1000):
    counter = [0]
    total = sum_halves(list(range(1, n + 1)), 0, n, counter)
    print(n, total, counter[0])
# Output:
# 1 1 1
# 2 3 3
# 8 36 15
# 100 5050 199
# 1000 500500 1999

The call count is always 2n - 1. For 8 values it is 15, and for 1,000 values it is 1,999. Hold that number in mind, because the next sections explain where it comes from.

#The Three Steps With a Picture

Draw the calls for 8 values as a tree. The root is the whole list. Each call has two children, the two halves. The leaves are the single values.

level 0:                 [ 8 values ]                  1 call, size 8
                        /            \
level 1:         [ 4 values ]      [ 4 values ]        2 calls, size 4
                  /      \          /      \
level 2:       [2]       [2]      [2]       [2]        4 calls, size 2
               / \       / \      / \       / \
level 3:      1   1     1   1    1   1     1   1       8 calls, size 1 (base case)

Count the calls: 1 + 2 + 4 + 8 = 15. That is the 15 in the output above. Divide happens on the way down the tree, conquer happens at the leaves, and combine happens on the way back up. The picture below shows the same shape for merge sort. In merge sort the divide step is nearly free (cut at the middle) and the combine step is the work (merge two sorted halves).

A quick recap of the two sorts you already know.

Merge sort halves the list, sorts each half, and merges the halves in one pass, so it is always O(n log n) and needs O(n) extra space.

Here we ask a different question: how do you find those costs for any divide and conquer function?

#Writing a Recurrence From Code

• a is the number of recursive calls the function makes.
• b says how much smaller each call's input is: the size is n divided by b.
• f(n) is the work done outside the recursive calls, which means dividing and combining.

The general shape is T(n) = a T(n/b) + f(n). Read each function this way.

Merge sort makes 2 calls on halves, then merges in a pass over n values. So T(n) = 2 T(n/2) + n.

Binary search makes 1 call on half of the list and does one comparison. So T(n) = T(n/2) + 1. Here a = 1.

#Solving a Recurrence: Count the Work Per Level

The recursion tree gives a method that needs no formula. Draw the tree, add up the work on each level, then add up the levels.

Check it with a counter. This merge sort records how many values each level merges.

def merge_sort_work(items, depth, work):
    """Merge sort that records, for each depth, how many items were merged."""
    if len(items) <= 1:
        return items
    mid = len(items) // 2
    left = merge_sort_work(items[:mid], depth + 1, work)
    right = merge_sort_work(items[mid:], depth + 1, work)
    work[depth] = work.get(depth, 0) + len(items)     # the merge touches every item once
    out, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            out.append(left[i]); i += 1
        else:
            out.append(right[j]); j += 1
    return out + left[i:] + right[j:]


for n in (16, 1024):
    work = {}
    merge_sort_work(list(range(n, 0, -1)), 0, work)
    print("n =", n, "merge work per level:", [work[d] for d in sorted(work)], "total", sum(work.values()))
# Output:
# n = 16 merge work per level: [16, 16, 16, 16] total 64
# n = 1024 merge work per level: [1024, 1024, 1024, 1024, 1024, 1024, 1024, 1024, 1024, 1024] total 10240

Every level costs n. The tree has log2 n levels of merging: 4 for 16 values and 10 for 1,024. So the total is n times log2 n, which is 64 and 10,240. That is O(n log n), and we found it by counting, not by guessing.

Now compare three recurrences. The function below really runs T(n) = a T(n/2) + f(n): it makes a calls on half the size and adds f(n) at each call. It then reports the work on the top level, the bottom level and the total, for n = 256.

import math


def tree_work(n, a, f, depth, per_level):
    """Run T(n) = a*T(n/2) + f(n) for real: make a calls on n//2, add f(n) at each call."""
    per_level[depth] = per_level.get(depth, 0) + f(n)
    if n > 1:
        for _ in range(a):
            tree_work(n // 2, a, f, depth + 1, per_level)


cases = [
    ("a=4, f(n)=n  ", 4, lambda n: n, "n^2", lambda n: n * n),
    ("a=2, f(n)=n  ", 2, lambda n: n, "n log n", lambda n: n * math.log2(n)),
    ("a=1, f(n)=n^2", 1, lambda n: n * n, "n^2", lambda n: n * n),
]
n = 256
for name, a, f, label, guess in cases:
    per_level = {}
    tree_work(n, a, f, 0, per_level)
    levels = [per_level[d] for d in sorted(per_level)]
    total = sum(levels)
    print(name, "top level:", levels[0], "bottom level:", levels[-1], "total:", total, f"total / {label} = {total / guess(n):.2f}")
# Output:
# a=4, f(n)=n   top level: 256 bottom level: 65536 total: 130816 total / n^2 = 2.00
# a=2, f(n)=n   top level: 256 bottom level: 256 total: 2304 total / n log n = 1.12
# a=1, f(n)=n^2 top level: 65536 bottom level: 1 total: 87381 total / n^2 = 1.33

Three different pictures. In the first, the bottom level is far bigger than the top, so the bottom decides the total. In the second, every level costs the same, so the total is one level times the number of levels. In the third, the top level is far bigger than the bottom, so the top decides the total. These are exactly the three cases of the master theorem.

#The Master Theorem

Compare a with b to the power d. The number a counts how fast the calls multiply on each level. The number b^d counts how fast the work per call shrinks on each level. There are three cases.

• Case 1: if a is greater than b^d, the work per level grows as you go down. The leaves dominate, and T(n) is O(n to the power log_b a).
• Case 2: if a equals b^d, the work per level stays the same. T(n) is O(n^d log n).
• Case 3: if a is less than b^d, the work per level falls as you go down. The top level dominates, and T(n) is O(n^d).

Here log_b a means the power you raise b to in order to get a. For a = 4 and b = 2 it is 2, because 2 squared is 4. For a = 3 and b = 2 it is about 1.585.

Work one example per case in plain words.

Case 1, leaves dominate: T(n) = 4 T(n/2) + n. Here a = 4, b = 2, d = 1, so b^d = 2. Since 4 is bigger than 2, each level has twice the work of the one above. The bottom level has 4 to the power log2 n calls, which is n squared. So T(n) is O(n²). The run above agrees: the total divided by n² was 2.00.

Case 2, balanced: T(n) = 2 T(n/2) + n, which is merge sort. Here a = 2 and b^d = 2, so they are equal. Every level costs n and there are log2 n levels. So T(n) is O(n log n). The run gave 1.12 times n log2 n.

Case 3, the top dominates: T(n) = T(n/2) + n². Here a = 1, b = 2, d = 2, so b^d = 4. Since 1 is less than 4, each level costs a quarter of the one above. The top level is almost everything. So T(n) is O(n²), and the run gave 1.33 times n².

Binary search is T(n) = T(n/2) + 1. Here a = 1, b = 2, d = 0, so b^d = 1 equals a, and case 2 gives O(n^0 log n), which is O(log n). The theorem agrees with the halving game from the start of this part.

The cell below makes a table of seven recurrences. It names the growth the theorem predicts, and it solves each recurrence exactly to show how much the cost grows when n doubles.

import math


def solve(n, a, b, d):
    """Exact T(n) = a*T(n/b) + n**d with T(1) = 1, for n a power of b."""
    return 1 if n == 1 else a * solve(n // b, a, b, d) + n ** d


def master(a, b, d):
    """Name the growth that the three cases of the master theorem give."""
    if a < b ** d:
        return f"n^{d}"
    if a == b ** d:
        return f"n^{d} log n"
    return f"n^{math.log(a, b):.3f}"


rows = [(1, 2, 1), (2, 2, 1), (3, 2, 1), (4, 2, 1), (2, 2, 2), (8, 2, 2), (2, 2, 0)]
for a, b, d in rows:
    n = b ** 10
    ratio = solve(b * n, a, b, d) / solve(n, a, b, d)
    print(f"a={a} b={b} d={d} -> {master(a, b, d):<9} T(bn)/T(n) = {ratio:.2f}")
# Output:
# a=1 b=2 d=1 -> n^1       T(bn)/T(n) = 2.00
# a=2 b=2 d=1 -> n^1 log n T(bn)/T(n) = 2.18
# a=3 b=2 d=1 -> n^1.585   T(bn)/T(n) = 3.01
# a=4 b=2 d=1 -> n^2.000   T(bn)/T(n) = 4.00
# a=2 b=2 d=2 -> n^2       T(bn)/T(n) = 4.00
# a=8 b=2 d=2 -> n^3.000   T(bn)/T(n) = 8.00
# a=2 b=2 d=0 -> n^1.000   T(bn)/T(n) = 2.00

Read the last column. Doubling n multiplied the cost by about 2 for the first row (linear), a bit over 2 for n log n, about 3 for n^1.585, and 4 for n squared. The row a=2, d=0 is the sum-by-halves recurrence, which is linear, and that matches the 2n - 1 calls we counted.

#When the Master Theorem Does Not Apply

The theorem is a tool with fixed rules. Check them before you use it.

It does not apply when the pieces are not all the same fraction of n. Quick sort with a bad pivot gives T(n) = T(n-1) + n, which shrinks by subtraction and not by division. A split into one third and two thirds, T(n) = T(n/3) + T(2n/3) + n, has two different sizes. For these, draw the recursion tree and add the levels yourself.

A stronger tool called Akra-Bazzi handles uneven splits, but we do not need it here.

It does not apply when a is not a constant, for example T(n) = n T(n/2) + 1. It does not apply when a is less than 1.

It does not apply when f(n) is not a plain power of n. For T(n) = 2 T(n/2) + n log n, the three cases above do not decide the answer. The tree method does: each level costs about n log n, and there are log n levels, so the total is O(n log² n). The full version of the theorem has a rule for this, but the short version here does not.

One more point: the theorem gives an upper bound in the form we wrote, and it needs a recurrence that really describes your code. If the code hides a copy or a sort inside the combine step, f(n) is bigger than you thought, and the answer changes with it.

The third mistake in Common Mistakes, near the end, measures one recurrence that is outside the rules. T(n) = T(n-1) + n has no b, and doubling n multiplies its cost by about 4, so it is O(n²).

#Binary Search and Fast Exponentiation

def search_slicing(items, x, copied):
    """Recursive binary search that passes a slice. copied[0] counts values copied by slicing."""
    if not items:
        return False
    mid = len(items) // 2
    if items[mid] == x:
        return True
    half = items[:mid] if x < items[mid] else items[mid + 1:]
    copied[0] += len(half)                  # slicing copies every value it keeps
    return search_slicing(half, x, copied)


def search_indexes(items, x, lo, hi, probes):
    """The same search with two indexes. probes[0] counts looks at the middle."""
    if lo >= hi:
        return False
    mid = (lo + hi) // 2
    probes[0] += 1
    if items[mid] == x:
        return True
    if x < items[mid]:
        return search_indexes(items, x, lo, mid, probes)
    return search_indexes(items, x, mid + 1, hi, probes)


for n in (1_000, 100_000):
    items = list(range(n))
    copied, probes = [0], [0]
    search_slicing(items, -1, copied)
    search_indexes(items, -1, 0, n, probes)
    print(n, "values copied by slicing:", copied[0], " probes with indexes:", probes[0])
# Output:
# 1000 values copied by slicing: 994  probes with indexes: 10
# 100000 values copied by slicing: 99994  probes with indexes: 17

The slice version has f(n) = n/2, so T(n) = T(n/2) + n/2, which is case 3 with O(n). The index version keeps f(n) = 1 and is O(log n), with O(log n) stack space.

Trace 3 to the power 13 by hand. The calls go 13, 6, 3, 1, 0. On the way back: from n=0 the value is 1. For n=1: 1 times 1 is 1, times 3 gives 3. For n=3: 3 times 3 is 9, times 3 gives 27. For n=6: 27 times 27 is 729. For n=13: 729 times 729 is 531,441, times 3 gives 1,594,323. That took 7 multiplications and not 12.

def power(x, n, counter):
    """x to the power n by squaring. counter[0] counts multiplications."""
    if n == 0:
        return 1
    half = power(x, n // 2, counter)       # ONE recursive call on half the exponent
    counter[0] += 1
    result = half * half
    if n % 2 == 1:
        counter[0] += 1
        result *= x
    return result


def power_naive(x, n, counter):
    result = 1
    for _ in range(n):
        counter[0] += 1
        result *= x
    return result


for n in (10, 1000, 10**6):
    fast, slow = [0], [0]
    a = power(3, n, fast)
    b = power_naive(3, n, slow) if n <= 1000 else None
    print(n, "fast multiplications:", fast[0], "naive:", slow[0] if b is not None else "skipped", "same answer:", b is None or a == b)
print(power(2, 100, [0]) == 2 ** 100)
# Output:
# 10 fast multiplications: 6 naive: 10 same answer: True
# 1000 fast multiplications: 16 naive: 1000 same answer: True
# 1000000 fast multiplications: 27 naive: skipped same answer: True
# True

The recurrence is T(n) = T(n/2) + 1: one call on half the exponent and a constant number of multiplications. By the master theorem (a = 1, b = 2, d = 0) that is O(log n) multiplications. A million needs only 27. The stack depth is also O(log n).

def pow_mod(x, n, m):
    """x**n % m by squaring, keeping every number below m."""
    if n == 0:
        return 1 % m
    half = pow_mod(x, n // 2, m)
    result = half * half % m               # reduce after every multiplication
    if n % 2 == 1:
        result = result * x % m
    return result


print(pow_mod(3, 200, 13), pow(3, 200, 13))
print(pow_mod(7, 10**18, 1_000_000_007), pow(7, 10**18, 1_000_000_007))
print(pow_mod(2, 0, 1))
# Output:
# 9 9
# 259616729 259616729
# 0

#Maximum Subarray: Divide and Conquer Versus Kadane

Divide and conquer cuts the list at the middle. The best run is in one of three places: entirely in the left half, entirely in the right half, or crossing the middle. The first two are recursive calls. The third needs a short loop: grow a run leftwards from the middle and remember its best sum, grow a run rightwards and remember its best sum, then add the two.

import random


def best_crossing(items, lo, mid, hi):
    """Best sum of a run that includes items[mid - 1] and items[mid]."""
    left_best, running = float("-inf"), 0
    for i in range(mid - 1, lo - 1, -1):         # grow leftwards from the middle
        running += items[i]
        left_best = max(left_best, running)
    right_best, running = float("-inf"), 0
    for i in range(mid, hi):                     # grow rightwards from the middle
        running += items[i]
        right_best = max(right_best, running)
    return left_best + right_best


def max_subarray_dc(items, lo, hi):
    """Divide and conquer: best of the left half, the right half, or a run across the middle."""
    if hi - lo == 1:
        return items[lo]
    mid = (lo + hi) // 2
    return max(max_subarray_dc(items, lo, mid),
               max_subarray_dc(items, mid, hi),
               best_crossing(items, lo, mid, hi))


def kadane(items):
    best = running = items[0]
    for x in items[1:]:
        running = max(x, running + x)            # extend the run, or start again here
        best = max(best, running)
    return best


data = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(max_subarray_dc(data, 0, len(data)), kadane(data))

random.seed(11)
agree = 0
for _ in range(300):
    arr = [random.randint(-9, 9) for _ in range(random.randint(1, 30))]
    agree += max_subarray_dc(arr, 0, len(arr)) == kadane(arr)
print("cases that agree:", agree, "of 300")
print(max_subarray_dc([-4, -2, -7], 0, 3), kadane([-4, -2, -7]))
# Output:
# 6 6
# cases that agree: 300 of 300
# -2 -2

The recurrence is T(n) = 2 T(n/2) + n: two half calls and a crossing loop over n values. That is case 2, so the time is O(n log n), and the stack uses O(log n) space.

Kadane's algorithm does it in one pass: for each value, either extend the current run or start a new run at this value. It is O(n) time and O(1) space. So Kadane is better here, and you should use it. The divide and conquer version is still worth knowing, because the three-way split (left, right, crossing) is a pattern that returns in other problems.

It also teaches a habit: after you solve a problem with a recurrence, ask whether a simpler pass does it faster. The answer for an all-negative list is the largest single value, -2 above, and both versions handle it.

#Counting Inversions With Merge Sort

Counting them with two loops is O(n²). Merge sort counts them for free. The inversions are of three kinds: both values in the left half, both in the right half, or one in each. The first two come from the recursive calls. The third is counted during the merge, because both halves are already sorted.

Next 2 beats 3, nothing added. Next 4 against 3: the 3 jumps over only the 4, so add 1. The total is 3: the pairs (2,1), (4,1) and (4,3).

import random


def sort_and_count(items):
    """Return (sorted copy, number of inversions). An inversion is a pair i < j with items[i] > items[j]."""
    if len(items) <= 1:
        return items, 0
    mid = len(items) // 2
    left, left_inv = sort_and_count(items[:mid])
    right, right_inv = sort_and_count(items[mid:])
    merged, i, j, cross = [], 0, 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            cross += len(left) - i       # right[j] jumps over everything still waiting in left
            j += 1
    merged += left[i:] + right[j:]
    return merged, left_inv + right_inv + cross


def brute_inversions(items):
    return sum(1 for i in range(len(items)) for j in range(i + 1, len(items)) if items[i] > items[j])


print(sort_and_count([2, 4, 1, 3, 5]))
print(sort_and_count([5, 4, 3, 2, 1])[1], sort_and_count([1, 2, 3, 4, 5])[1])

random.seed(5)
data = random.sample(range(10_000), 2000)
print(sort_and_count(data)[1], brute_inversions(data))
print("brute force pair checks:", 2000 * 1999 // 2)
# Output:
# ([1, 2, 3, 4, 5], 3)
# 10 0
# 980623 980623
# brute force pair checks: 1999000

#Quickselect: The k-th Largest Without Sorting

The code below loops instead of recursing, because quickselect follows only one branch. It counts how many times an item is checked against a pivot.

import random


def quickselect(items, k, pick, counter):
    """k-th largest (k = 1 is the biggest). Loops instead of recursing. counter[0] counts item-versus-pivot checks."""
    pool = list(items)
    while True:
        pivot = pick(pool)
        bigger, equal, smaller = [], [], []
        for x in pool:                            # one pass: every item is checked against the pivot once
            if x > pivot:
                bigger.append(x)
            elif x == pivot:
                equal.append(x)
            else:
                smaller.append(x)
        counter[0] += len(pool)
        if k <= len(bigger):
            pool = bigger                         # the answer is among the bigger ones
        elif k <= len(bigger) + len(equal):
            return pivot                          # the pivot itself is the k-th largest
        else:
            k -= len(bigger) + len(equal)         # skip them, look among the smaller ones
            pool = smaller


random.seed(3)
data = random.sample(range(100_000), 10_001)
ranked = sorted(data, reverse=True)
for k in (1, 5_001, 10_001):
    print(k, quickselect(data, k, random.choice, [0]) == ranked[k - 1])

for n in (1_000, 10_000, 100_000):
    arr = random.sample(range(10 * n), n)
    total = 0
    for _ in range(20):
        c = [0]
        quickselect(arr, n // 2, random.choice, c)
        total += c[0]
    print(n, "checks per item for the median, averaged over 20 runs:", round(total / 20 / n, 1))

# the bad pivot: always take the first item of a list that is already sorted, and ask for the biggest
for n in (500, 1_000, 2_000):
    c = [0]
    quickselect(list(range(n)), 1, lambda pool: pool[0], c)
    print(n, "checks with a first-item pivot on sorted input:", c[0], " n*(n+1)/2 =", n * (n + 1) // 2)
# Output:
# 1 True
# 5001 True
# 10001 True
# 1000 checks per item for the median, averaged over 20 runs: 3.2
# 10000 checks per item for the median, averaged over 20 runs: 3.5
# 100000 checks per item for the median, averaged over 20 runs: 3.2
# 500 checks with a first-item pivot on sorted input: 125250  n*(n+1)/2 = 125250
# 1000 checks with a first-item pivot on sorted input: 500500  n*(n+1)/2 = 500500
# 2000 checks with a first-item pivot on sorted input: 2001000  n*(n+1)/2 = 2001000

With a random pivot the checks per item stay near 3 or 4 however big n grows. That flat line is what O(n) looks like. With the first item as pivot on sorted data, every pass removes just one value, and the total is n(n+1)/2, which is O(n²).

Here is the reasoning, informally. A random pivot lands in the middle half of the sorted order half the time. Then at most three quarters of the values remain. So on average about every two passes shrink the pool to three quarters, which gives roughly T(n) = T(3n/4) + 2n. In the master theorem a = 1, b = 4/3 and d = 1, so a is less than b^d, which is case 3 and gives O(n).

This is an argument and not a proof, but the measured numbers agree.

The expected time is O(n). The worst case is O(n²), and it needs a very unlucky run of pivots, so a random pivot makes it rare. It is the same story as quick sort. The version above uses O(n) extra space for the three lists; an in-place version needs O(1) extra space.

That pivot is guaranteed to be near enough the middle that each pass discards a fixed fraction of the values, and the work adds up to O(n) even in the worst case. We do not prove it here.

#Karatsuba: Fewer Multiplications

Multiply two numbers of n digits the way you did at school, and every digit of one meets every digit of the other: n times n small multiplications, O(n²). Karatsuba showed that divide and conquer can do better, by saving one multiplication.

Split each number in two halves of digits. Write x = a times 10^m plus b, and y = c times 10^m plus d. Then x times y is a·c times 10^(2m), plus (a·d + b·c) times 10^m, plus b·d. That looks like four half-size multiplications.

The trick: (a+b) times (c+d) equals a·c + a·d + b·c + b·d. So the middle part, a·d + b·c, is (a+b)(c+d) minus a·c minus b·d. We already have a·c and b·d, so the middle part costs one more multiplication, not two. Three half-size multiplications instead of four.

Check with 1234 times 5678. Here a=12, b=34, c=56, d=78. Then a·c = 672 and b·d = 2,652. The sum product is (12+34)(56+78) = 46 times 134 = 6,164. The middle is 6,164 - 672 - 2,652 = 2,840. The answer is 672 times 10,000 + 2,840 times 100 + 2,652 = 7,006,652.

The recurrence is T(n) = 3 T(n/2) + n: three calls on half the digits, plus additions and shifts that cost O(n). Here a = 3, b = 2, d = 1, and b^d = 2 is less than 3, so this is case 1: the leaves dominate and T(n) is O(n to the power log2 3), about O(n^1.585). Run it against Python's own integers.

import math
import random


def karatsuba(x, y, counter):
    """Multiply two non-negative ints. counter[0] counts one-digit multiplications."""
    if x < 10 or y < 10:
        counter[0] += 1                              # a one-digit multiplication
        return x * y
    m = max(len(str(x)), len(str(y))) // 2
    x_hi, x_lo = divmod(x, 10 ** m)                  # x = x_hi * 10^m + x_lo
    y_hi, y_lo = divmod(y, 10 ** m)
    a = karatsuba(x_hi, y_hi, counter)               # hi * hi
    b = karatsuba(x_lo, y_lo, counter)               # lo * lo
    c = karatsuba(x_hi + x_lo, y_hi + y_lo, counter) # (hi + lo) * (hi + lo): the third call
    middle = c - a - b                               # equals x_hi*y_lo + x_lo*y_hi
    return a * 10 ** (2 * m) + middle * 10 ** m + b


def schoolbook_count(x, y):
    """One-digit multiplications by the method taught at school: every digit of x with every digit of y."""
    return len(str(x)) * len(str(y))


random.seed(2)
print(karatsuba(1234, 5678, [0]), 1234 * 5678)
ok = 0
for _ in range(200):
    x, y = random.randrange(10 ** 40), random.randrange(10 ** 40)
    ok += karatsuba(x, y, [0]) == x * y
print("matches Python's *:", ok, "of 200")

for digits in (8, 64, 512, 2048):
    x = random.randrange(10 ** (digits - 1), 10 ** digits)
    y = random.randrange(10 ** (digits - 1), 10 ** digits)
    c = [0]
    karatsuba(x, y, c)
    print(digits, "digits: karatsuba", c[0], "school", schoolbook_count(x, y))
print("log2(3) =", round(math.log2(3), 3))
# Output:
# 7006652 7006652
# matches Python's *: 200 of 200
# 8 digits: karatsuba 41 school 64
# 64 digits: karatsuba 1089 school 4096
# 512 digits: karatsuba 28713 school 262144
# 2048 digits: karatsuba 256897 school 4194304
# log2(3) = 1.585

At 8 digits the saving is small. At 2,048 digits Karatsuba needs about 257,000 one-digit multiplications against more than 4 million. Each time the digits grow 8 times (64 to 512), the schoolbook count grows 64 times and Karatsuba grows 27 times, which is 3 to the power 3.

#Closest Pair of Points: The Idea

Given n points on a plane, which two are closest? The plain method checks all pairs, n(n-1)/2 of them, which is O(n²). The cell below does that for a small set.

import math


def closest_pair_brute(points):
    """Compare every pair: n*(n-1)/2 distances. The baseline that divide and conquer beats."""
    best = (math.inf, None)
    for i in range(len(points)):
        for j in range(i + 1, len(points)):
            d = math.dist(points[i], points[j])
            if d < best[0]:
                best = (d, (points[i], points[j]))
    return best


pts = [(0, 0), (7, 1), (3, 4), (3, 5), (9, 9), (1, 8)]
d, pair = closest_pair_brute(pts)
print(round(d, 3), pair)
print("pairs checked for 6 points:", 6 * 5 // 2, " for 1000 points:", 1000 * 999 // 2)
# Output:
# 1.0 ((3, 4), (3, 5))
# pairs checked for 6 points: 15  for 1000 points: 499500

The divide and conquer idea has three steps, and we describe them without the full code.

Divide: sort the points by x and cut with a vertical line at the middle. Conquer: find the closest pair on each side. Call the smaller of the two distances d. Combine: the true closest pair may have one point on each side. But such a pair must lie in a thin strip of width 2d around the line, because any pair farther apart than d cannot beat what we already have.

The surprise is how few checks the strip needs. Sort its points by y.

For each point you only need to compare it with a small constant number of the next points, at most 7 in the common textbook version, because only a few points can fit in a d by 2d box when all points on each side are at least d apart.

So the combine step is O(n), the recurrence is T(n) = 2 T(n/2) + n, and the time is O(n log n) against O(n²). This is a geometry problem solved by the same recurrence as merge sort.

#Divide and Conquer Versus Dynamic Programming

Both solve a problem by solving smaller versions. The difference is one question: do the smaller problems overlap? In divide and conquer the pieces are separate. Merge sort never sorts the same piece twice. In dynamic programming the same small question is asked again and again, so we store each answer.

Count the different questions that each method asks.

def fib_calls(n, seen):
    """Naive Fibonacci. seen collects which n values were asked for."""
    seen.append(n)
    if n < 2:
        return n
    return fib_calls(n - 1, seen) + fib_calls(n - 2, seen)


def merge_sort_ranges(lo, hi, seen):
    """Which (lo, hi) slices does merge sort ask about?"""
    seen.append((lo, hi))
    if hi - lo > 1:
        mid = (lo + hi) // 2
        merge_sort_ranges(lo, mid, seen)
        merge_sort_ranges(mid, hi, seen)


for name, run in (("fib(20)", lambda s: fib_calls(20, s)), ("merge sort on 16", lambda s: merge_sort_ranges(0, 16, s))):
    seen = []
    run(seen)
    print(f"{name}: {len(seen)} calls, {len(set(seen))} different questions")
# Output:
# fib(20): 21891 calls, 21 different questions
# merge sort on 16: 31 calls, 31 different questions

Fibonacci made 21,891 calls to answer only 21 different questions, so it repeats itself heavily and a cache turns it into 21 calls. Merge sort made 31 calls and 31 different questions, so a cache would save nothing. The tree below shows the repeats for Fibonacci. Open the Comparison tab and watch the cached branches disappear.

Use this test on any new problem. Write the recursion, then ask whether two different branches can reach the same subproblem. If yes, use memoization or a table (see the Recursion and Dynamic Programming lessons). If no, plain divide and conquer is right, and a cache would only use memory.

#A Word on Parallelism

The pieces of a divide and conquer problem do not depend on each other. Two halves of a list can be sorted at the same moment on two workers, and that is why this pattern is popular for big jobs. The combine step usually has to wait for both halves, so some part of the work stays one after another, and that limits the speed-up.

This browser cannot show you that. Python in the browser (Pyodide) runs in one thread: there are no threads or processes, so every cell in this lesson runs one step after another. We show nothing parallel on purpose, because a demonstration would be pretend.

On a normal computer, CPython's global interpreter lock lets only one thread run Python code at a time, so CPU-heavy parallel work usually uses separate processes. The cost formulas above count total work, and they stay true whether the work is shared or not.

#When Not to Use It

Divide and conquer is not always the right tool. Watch for these cases.

• The pieces overlap. Use dynamic programming, as above.
• The combine step is as costly as the whole problem. If f(n) is large, splitting gains nothing.
• The input is tiny. Recursive calls cost time, so real libraries switch to a simple loop below some size.
• A direct loop already does it in O(n). Kadane beats the divide and conquer version of maximum subarray.
• The recursion would be very deep. Python's default limit is about 1,000 calls. Halving gives depth log n, which is safe, but splitting off one value at a time is not.

#Where It Shows Up

Sorting in databases and in languages is built from merging. External sorting, for files too big for memory, sorts pieces and merges them. A k-d tree, used to find nearby points, splits the points at the median, which is a quickselect job.

Top-k selection, such as the 10 highest-scoring results, uses partitioning or a heap instead of a full sort.

The fast Fourier transform, used in signal processing, is a divide and conquer algorithm, and so is Strassen's matrix multiplication, which uses 7 half-size multiplications instead of 8. Splitting work across machines and joining results, as in MapReduce, has the same three steps. None of these needs you to remember a formula. They need you to ask what the recurrence is.

#The Costs in One Table

All sizes are n values. The time column comes from the recurrence, and the space column counts extra memory including the call stack.

#Common Mistakes

#Try It

Work the ladder in order. Each rung has a stub with a TODO and an Expected line. Rung 1 writes a first recursion and counts its calls, rung 2 applies squaring to a matrix, rung 3 splits a list of lists, rung 4 is a function with two bugs, and rung 5 turns inversion counting into a harder question.

Hints: in rung 1 the recurrence is T(n) = 2T(n/2) + 1, and a tree with 8 leaves has 15 nodes.

#Recap

Divide and conquer splits a problem into smaller copies of itself, solves each one, and combines the answers. The cost is a recurrence T(n) = a T(n/b) + f(n): a calls, each on n/b of the input, plus f(n) work to divide and combine.

You can solve it by counting the work per level of the recursion tree, and the master theorem gives the answer by comparing a with b to the power d. It does not apply to uneven splits, to shrinking by subtraction, or to an f(n) that is not a plain power.

The pattern gives fast powers in O(log n) multiplications, O(n log n) maximum subarray (though Kadane is O(n)), inversion counting in O(n log n), quickselect in O(n) expected and O(n²) worst, and Karatsuba in about O(n^1.585).

Check hidden copies such as slices, and ask whether the subproblems overlap: if they do, use dynamic programming.