Divide & conquer + Master theorem

1 · The paradigm and its recurrence advanced

Think about how you actually find a word in a physical dictionary. You don't start at "aardvark" and read forward — that would take all afternoon. You flop it open near the middle, decide "too far" or "not far enough," and flop again into the half that must contain your word. Each flop throws away half the book. Nobody taught you a recurrence relation to do this; it's just obvious that splitting the problem beats grinding through it. Divide-and-conquer is that instinct written down as an algorithm design technique — and once you name it, you start seeing it in sorting, searching, multiplication, even geometry.

Here's the everyday analogy that makes the three steps stick. Imagine you're a manager handed a giant stack of invoices to total. You could add them one by one (linear, slow, and you do all the work). Or you split the stack in half, hand each half to a teammate, wait for their two subtotals, and add those two numbers together. Each teammate, faced with their own pile, does the same thing — splits and delegates — until someone is holding a single invoice and just reads off its value. That's the whole paradigm: divide the work, conquer the pieces by the same method (recursion), then combine the answers. The magic isn't in any one step; it's that the same simple rule applies all the way down.

The common mistake is to assume that splitting is always a win. It isn't — divide-and-conquer only pays off when two things are true: the subproblems are genuinely independent (your teammates don't need to talk to each other), and the combine step is cheap relative to the work you saved. If combining the halves costs as much as solving the whole thing directly, you've gained nothing but overhead. That tension — how much does combine cost versus how much did dividing save? — is the entire subject of the Master theorem in the next section, so hold onto it.

A divide-and-conquer algorithm has three steps. Divide the input of size n into a subproblems, each of size n/b. Conquer each subproblem by recursion (a base case stops the recursion). Combine the sub-answers into the answer, doing f(n) work. The total cost obeys a recurrence relation:

T(n) = a·T(n/b) + f(n), with T(1) = Θ(1).

Everything in this lesson is a special case. Merge sort splits into a=2 halves (b=2) and merges in f(n)=Θ(n). Binary search recurses into a=1 half and does Θ(1) work. The whole game is: write the recurrence, then solve it.

2 · The Master theorem — all three cases expert

Every time you write a recursive divide-and-conquer function, you've quietly created a debt you owe your future self: what is this thing's Big-O? You could grind it out by hand — draw the recursion tree, sum every level, spot the pattern — and that's a genuinely useful skill you'll practice in §3. But you'll do it dozens of times for the same shape of recurrence, and mathematicians noticed that most divide-and-conquer recurrences fall into just three buckets. The Master theorem is the lookup table that reads off the answer, so you don't re-derive it every time.

Here's the intuition, and it's a genuinely simple tug-of-war once you see it. A recursion tree has two kinds of work fighting for dominance. At the very bottom are the leaves — a huge number of tiny base-case problems; that's the n^(log_b a) term, which counts how the number of leaves explodes as you recurse. At the top and middle is the combine work f(n) — the merging, the partitioning, the "put the pieces back together" cost at each level. The question the theorem answers is simply: which of these two grows faster as n gets big? The bigger one wins and sets the overall complexity, exactly like the "biggest term dominates" rule from D1.

So the three cases aren't three arbitrary rules to memorize — they're the three possible outcomes of one tug-of-war. Case 1: the leaves win (there's so much branching that the bottom of the tree dwarfs everything above it). Case 3: the combine work at the root wins (each merge is so expensive that the top level dominates). Case 2: it's a genuine tie — leaf work and combine work are the same size at every level, so every level costs the same and you pay that cost once per level, which is where the extra log n factor sneaks in (there are log n levels). That tie is why merge sort is n log n and not just n.

The mistake almost everyone makes is treating the Master theorem as a universal solver and getting burned when it silently doesn't apply. It only covers recurrences of the exact form a·T(n/b)+f(n) where the subproblems are all the same size, and even then it fails in the awkward zone where f(n) is bigger than the watershed but not polynomially bigger (the warning box below has the classic trap). It says nothing about recurrences like T(n-1)+T(n-2) (Fibonacci) or uneven splits. When in doubt, fall back to the recursion tree — the theorem is a shortcut, not a substitute for understanding.

The Master theorem solves T(n)=a·T(n/b)+f(n) for constants a≥1, b>1. Compare f(n) against the watershed function n^(log_b a) — the cost of the leaves of the recursion tree. The bigger of {leaf work, combine work} dominates.

Worked examples. Merge sort: a=2, b=2 so log_b a = log₂2 = 1, and f(n)=Θ(n)=Θ(n¹) — that is Case 2, giving Θ(n log n). Binary search: a=1, b=2, log₂1 = 0, f(n)=Θ(1)=Θ(n⁰) — Case 2 again, Θ(log n). Naive matrix mult of two n×n via 8 half-size products: a=8, b=2, log₂8 = 3, f(n)=Θ(n²) which is smaller — Case 1, Θ(n³). Strassen shaves a to 7: log₂7 ≈ 2.807, still Case 1, Θ(n^2.807).

pythonimport math

def master_case(a, b, f_exp):
    """a, b as in T(n)=a T(n/b)+f(n); f_exp = exponent p in f(n)=Theta(n^p)."""
    watershed = math.log(a, b)              # log_b(a)
    if abs(f_exp - watershed) < 1e-9:
        return f"Case 2: T(n) = Theta(n^{watershed:.3f} * log n)"
    if f_exp < watershed:
        return f"Case 1: T(n) = Theta(n^{watershed:.3f})"
    return f"Case 3: T(n) = Theta(n^{f_exp:.3f})"

print("merge sort   ", master_case(2, 2, 1))    # a=2,b=2,f=n^1
print("binary search", master_case(1, 2, 0))    # a=1,b=2,f=n^0
print("naive matmul ", master_case(8, 2, 2))    # a=8,b=2,f=n^2
print("Strassen     ", master_case(7, 2, 2))    # a=7,b=2,f=n^2
print("Karatsuba    ", master_case(3, 2, 1))    # a=3,b=2,f=n^1

merge sort    Case 2: T(n) = Theta(n^1.000 * log n)
binary search Case 2: T(n) = Theta(n^0.000 * log n)
naive matmul  Case 1: T(n) = Theta(n^3.000)
Strassen      Case 1: T(n) = Theta(n^2.807)
Karatsuba     Case 1: T(n) = Theta(n^1.585)

3 · Merge sort — D&C you can prove advanced

Picture two friends who have each already sorted their half of a deck of cards, and now need to combine them into one sorted pile. They don't reshuffle everything. Each holds their half face-up, looks at just the top card of each, and lays down the smaller one — then compares the two new tops, and again, and again. Because both halves are already in order, they only ever look at the current top of each pile, so the whole merge takes one pass. That physical move — zippering two sorted piles into one — is the heart of merge sort, and it's the one detail that makes the entire algorithm provably fast.

Merge sort matters for a reason beyond speed: it's the divide-and-conquer algorithm whose complexity you can prove on the back of a napkin, which makes it the teaching workhorse for the whole recurrence-tree method. Quicksort is faster in practice but its analysis is probabilistic and slippery; merge sort's cost is dead simple to reason about because every merge is honestly linear and the split is always exactly in half. When an interviewer asks you to "derive the complexity," merge sort is the one you want to be talking about, because the argument is airtight.

There's also a practical reason it earns its keep in real systems: merge sort is stable (equal elements keep their original order — priceless when you sort records by one field after another) and it merges sequentially, which means it can sort data far too big to fit in memory by streaming sorted runs off disk. That's exactly how databases do external sorts. The one gotcha to name: the tidy version you'll write below allocates a new list on every merge, so it uses O(n) extra space — unlike quicksort's in-place partitioning. That memory cost is the price of the clean proof, and it's usually a trade worth making.

Merge sort splits the array in half, sorts each half recursively, and merges two sorted halves in linear time. The merge is the combine step; its linearity is what pins f(n)=Θ(n) and hence Θ(n log n).

pythondef merge(left, right):
    out, i, j = [], 0, 0
    while i < len(left) and j < len(right):     # each comparison consumes one element
        if left[i] <= right[j]:
            out.append(left[i]); i += 1
        else:
            out.append(right[j]); j += 1
    out.extend(left[i:]); out.extend(right[j:])
    return out

def merge_sort(a):
    if len(a) <= 1:                             # base case: T(1)=O(1)
        return a
    mid = len(a) // 2
    left = merge_sort(a[:mid])                  # a=2 subproblems
    right = merge_sort(a[mid:])                 # ...each of size n/2
    return merge(left, right)                   # combine in Theta(n)

data = [5, 2, 9, 1, 7, 3, 8, 4, 6, 0]
print(merge_sort(data))
print("stable + correct:", merge_sort(data) == sorted(data))

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
stable + correct: True

Proof sketch. T(n)=2T(n/2)+cn. Expand the recursion tree: level i has 2^i nodes each doing c·n/2^i work — so every level costs cn. There are log₂n + 1 levels, giving cn·(log₂n+1)=Θ(n log n). The merge's linearity is the load-bearing fact: each of the n elements is copied once per level.

4 · Quickselect — expected linear time advanced

You want the median salary at a 10,000-person company. Do you need to line all 10,000 people up in order? No — you only need the one in the middle. Yet the reflex, drilled into every beginner, is "to find a ranked element, sort the list and index into it." That works, but it's wasteful: sorting arranges all 10,000 people just so you can read off one. You did n log n work to answer a question that, it turns out, only needs n. Quickselect is what you use when you catch yourself sorting-just-to-pick.

The trick is a small twist on quicksort's partition step, and the analogy is a scavenger hunt in a library. You grab a random book (the pivot), and split every other book into "comes before this one" and "comes after this one." Now — and this is the whole insight — you look at where your target rank falls. If you're hunting for the 300th smallest and the "before" pile has 4,000 books, your answer is definitely in that pile, so you throw the other 6,000 away entirely and recurse into just the one side. Quicksort has to sort both piles because it wants everything ordered; quickselect only cares about one specific rank, so it can discard half the problem at every step. That "recurse into one side, not both" is the entire difference, and it's what collapses 2T(n/2) into T(n/2).

Why does throwing away half each time give O(n) and not O(n log n)? Because the work shrinks geometrically: you scan n, then about n/2, then n/4, and n + n/2 + n/4 + … sums to 2n — a constant multiple of n, not n times log n. The geometric series is the mathematical reason a one-sided recursion is linear. The mistake to avoid is trusting this blindly: quickselect's beautiful O(n) is an average, not a guarantee. If you always pick a terrible pivot — say, the smallest element every time — each partition only peels off one element and you degrade to O(n²), the same trap that bites naive quicksort. The fix (a random pivot) is in the code below, and the callout after it explains why randomness makes the disaster case astronomically unlikely.

To find the k-th smallest element you do not need to sort. Quickselect partitions around a pivot (like quicksort) but recurses into only one side — the side containing rank k. Because it discards half the work on average, the recurrence is T(n)=T(n/2)+Θ(n), which sums to Θ(n) (a geometric series, not n log n).

pythonimport random

def quickselect(a, k):
    """Return the k-th smallest (0-indexed) element of list a."""
    if len(a) == 1:
        return a[0]
    pivot = random.choice(a)
    lo = [x for x in a if x < pivot]
    eq = [x for x in a if x == pivot]
    hi = [x for x in a if x > pivot]
    if k < len(lo):
        return quickselect(lo, k)               # recurse ONE side only
    if k < len(lo) + len(eq):
        return pivot                            # k lands in the pivot block
    return quickselect(hi, k - len(lo) - len(eq))

random.seed(7)
data = [5, 2, 9, 1, 7, 3, 8, 4, 6, 0]
got = [quickselect(data[:], k) for k in range(len(data))]
print("selected in rank order:", got)
print("matches sorted:", got == sorted(data))

selected in rank order: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
matches sorted: True

5 · Binary search variants — the off-by-one minefield intermediate

Here's a humbling fact from software history: binary search is four lines of idea, and yet a bug in the standard version lurked undetected in Java's core library — and in Jon Bentley's textbook implementation — for two decades. Bentley reported that when he taught the algorithm to professional programmers, roughly 90% wrote a broken version even after he'd explained it. The concept — "keep halving" — is trivial. The boundaries — where exactly does lo and hi land, is mid included or excluded, when do you stop — are where careers go to die. This section is less about the idea and more about a discipline that makes the boundaries stop hurting.

Start with why plain binary search isn't enough in the real world. Textbook binary search answers "is x in the array, yes or no?" But real questions are fuzzier and more useful: "where would I insert this to keep the list sorted?" or "how many copies of this value are there?" or "what's the first entry on or after this timestamp?" Those need the two workhorse variants — lower_bound (the first slot where a[i] ≥ target) and upper_bound (the first slot where a[i] > target). Subtract one from the other and you get the count of matching elements; either one alone gives you an insertion point. This is exactly what powers "find all log lines between 2pm and 3pm" over a sorted timestamp column without scanning the whole file.

The analogy that keeps beginners sane is to picture the interval as half-open — written [lo, hi), meaning lo is included but hi is not, like a range that owns its left fence post but stops just short of the right one. That single convention resolves most off-by-one agony, because "the answer is somewhere in [lo, hi)" stays true at every step, and when lo == hi the window is empty and you're done. The specific mistake that catches everyone: when mid could itself be the answer, you must set hi = mid — not hi = mid - 1 — or you'll step right over the element you were looking for. Mixing mid, mid+1, and mid-1 inconsistently is precisely how the two-decade bugs happened. Pick the half-open convention, apply it religiously, and the minefield turns into a checklist. (And in production, reach for Python's bisect_left/bisect_right — they are these two functions, already debugged.)

Binary search is D&C with a=1: halve the search space each step, Θ(log n). The subtlety is not the idea but the boundaries. Two workhorse variants: lower_bound (first index with a[i] ≥ target) and upper_bound (first index with a[i] > target). Together they give the range of equal elements and an insertion point.

pythondef lower_bound(a, target):
    lo, hi = 0, len(a)                          # half-open interval [lo, hi)
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] < target:
            lo = mid + 1                        # mid too small -> discard left half
        else:
            hi = mid                            # keep mid as a candidate
    return lo

def upper_bound(a, target):
    lo, hi = 0, len(a)
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] <= target:
            lo = mid + 1
        else:
            hi = mid
    return lo

a = [1, 2, 2, 2, 4, 6, 6, 9]
lb, ub = lower_bound(a, 2), upper_bound(a, 2)
print("first >= 2 at index", lb, "; first > 2 at index", ub)
print("count of 2s:", ub - lb)
print("insertion point for 5:", lower_bound(a, 5))

first >= 2 at index 1 ; first > 2 at index 4
count of 2s: 3
insertion point for 5: 5

6 · Karatsuba & closest-pair — beating the obvious bound expert

In 1960, the great mathematician Andrey Kolmogorov stood in front of a seminar and conjectured that multiplying two n-digit numbers must cost Θ(n²) — that the schoolbook method you learned as a child was essentially optimal. A 23-year-old student named Anatoly Karatsuba heard this, went home, and within a week had broken it. His trick shaved the exponent below 2, and Kolmogorov was so struck that he published the result under Karatsuba's name. That story is worth carrying because it teaches the real lesson of this whole lesson: an "obvious" lower bound is often just a failure of imagination about the combine step.

Here's the everyday intuition for what Karatsuba saw. To multiply two two-part numbers the naive way, you compute four sub-products — high×high, high×low, low×high, low×low — the same "multiply every part by every part" grid you'd draw for (a+b)(c+d). Four multiplications, and multiplication is the expensive operation. Karatsuba noticed you're doing redundant work: the two middle products (high×low and low×high) only ever appear added together in the answer, never separately. And there's an algebraic sleight of hand — compute (high+low)×(high+low), then subtract off the high×high and low×low you already have — that recovers that combined middle term with just one multiplication instead of two. Additions are cheap; multiplications are dear; so trading a multiply for a few adds is a bargain. Four multiplications become three.

Why does turning 4 into 3 matter so much? Because it's not a one-time saving — it changes the branching factor of the recursion, and that compounds at every level all the way down. In Master-theorem terms it drops a from 4 to 3, moving the exponent from log₂4 = 2 down to log₂3 ≈ 1.585. On numbers with thousands of digits (cryptography, arbitrary-precision arithmetic) that gap is enormous. The closest-pair-of-points algorithm later in this section is the same story wearing different clothes: the naive way compares all n² pairs, but a clever combine step — proving you only ever need to check a handful of points in a narrow strip around the dividing line — cuts it to Θ(n log n). The trap to avoid is assuming these tricks are free in practice: Karatsuba's extra additions and recursion overhead make it slower than schoolbook on small numbers, which is why real libraries only switch to it above a size threshold. The asymptotic win is real, but constants still decide who wins on your actual inputs.

Schoolbook multiplication of two n-digit numbers is Θ(n²). Karatsuba splits each number into high/low halves and observes that the three products it needs can be computed with three half-size multiplications instead of four (using (a+b)(c+d) = ac + bd + (ad+bc) to recover the cross term). That drops a from 4 to 3: T(n)=3T(n/2)+Θ(n) = Θ(n^log₂3) ≈ Θ(n^1.585).

pythondef karatsuba(x, y):
    if x < 10 or y < 10:                         # base case: single digit
        return x * y
    n = max(len(str(x)), len(str(y)))
    half = n // 2
    high_x, low_x = divmod(x, 10 ** half)
    high_y, low_y = divmod(y, 10 ** half)
    z0 = karatsuba(low_x, low_y)                 # bd
    z2 = karatsuba(high_x, high_y)               # ac
    z1 = karatsuba(low_x + high_x, low_y + high_y) - z2 - z0   # ad+bc via ONE mult
    return z2 * 10 ** (2 * half) + z1 * 10 ** half + z0

import random
random.seed(1)
ok = all(karatsuba(a, b) == a * b
         for a, b in ((random.randint(0, 10**12), random.randint(0, 10**12))
                      for _ in range(1000)))
print("1000 random products all correct:", ok)
print("example:", karatsuba(1234567, 89012345), "==", 1234567 * 89012345)

1000 random products all correct: True
example: 109891703729615 == 109891703729615

Closest pair of points is the geometric classic: sort by x, split at the median x, recursively find the closest pair in each half (distance δ), then check only points within a 2δ-wide strip around the split line. A packing argument shows each strip point compares against at most 7 others, so the combine is Θ(n) — giving T(n)=2T(n/2)+Θ(n)=Θ(n log n), beating the Θ(n²) all-pairs check.

Checkpoint expert

pythondef power(x, n):
    if n == 0:
        return 1
    half = power(x, n // 2)          # ONE recursive call -> O(log n)
    half_sq = half * half
    return half_sq * x if n % 2 else half_sq

print([power(2, k) for k in range(11)])
print("2^10 =", power(2, 10), "check:", power(2, 10) == 2 ** 10)
print("3^13 =", power(3, 13), "check:", power(3, 13) == 3 ** 13)

[1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024]
2^10 = 1024 check: True
3^13 = 1594323 check: True

pythondef sort_count(a):
    if len(a) <= 1:
        return a, 0
    mid = len(a) // 2
    left, cl = sort_count(a[:mid])
    right, cr = sort_count(a[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]); j += 1
            cross += len(left) - i         # all remaining left > right[j]
    merged.extend(left[i:]); merged.extend(right[j:])
    return merged, cl + cr + cross

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

data = [2, 4, 1, 3, 5, 0]
sorted_a, inv = sort_count(data)
print("sorted:", sorted_a, "inversions:", inv)
print("brute matches:", inv == brute(data))

sorted: [0, 1, 2, 3, 4, 5] inversions: 8
brute matches: True

pythondef search_rotated(a, target):
    lo, hi = 0, len(a) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if a[mid] == target:
            return mid
        if a[lo] <= a[mid]:                 # left half [lo..mid] is sorted
            if a[lo] <= target < a[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:                               # right half [mid..hi] is sorted
            if a[mid] < target <= a[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1

arr = [4, 5, 6, 7, 0, 1, 2]
print([search_rotated(arr, t) for t in (0, 4, 2, 7, 3)])
# indices of 0,4,2,7 and -1 for missing 3

[4, 0, 6, 3, -1]

pythondef max_subarray(a):
    def solve(lo, hi):
        if lo == hi:
            return a[lo]
        mid = (lo + hi) // 2
        left = solve(lo, mid)
        right = solve(mid + 1, hi)
        # best suffix ending at mid
        s, best_l = 0, float("-inf")
        for i in range(mid, lo - 1, -1):
            s += a[i]; best_l = max(best_l, s)
        # best prefix starting at mid+1
        s, best_r = 0, float("-inf")
        for i in range(mid + 1, hi + 1):
            s += a[i]; best_r = max(best_r, s)
        return max(left, right, best_l + best_r)
    return solve(0, len(a) - 1)

def kadane(a):
    best = cur = a[0]
    for x in a[1:]:
        cur = max(x, cur + x); best = max(best, cur)
    return best

data = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print("D&C:", max_subarray(data), "Kadane:", kadane(data))
print("match:", max_subarray(data) == kadane(data))

D&C: 6 Kadane: 6
match: True

pythondef median_two(a, b):
    if len(a) > len(b):
        a, b = b, a                          # ensure a is smaller
    m, n = len(a), len(b)
    lo, hi, half = 0, m, (m + n + 1) // 2
    while lo <= hi:
        i = (lo + hi) // 2                   # cut in a
        j = half - i                         # cut in b
        a_left = a[i - 1] if i > 0 else float("-inf")
        a_right = a[i] if i < m else float("inf")
        b_left = b[j - 1] if j > 0 else float("-inf")
        b_right = b[j] if j < n else float("inf")
        if a_left <= b_right and b_left <= a_right:
            if (m + n) % 2:
                return float(max(a_left, b_left))
            return (max(a_left, b_left) + min(a_right, b_right)) / 2
        if a_left > b_right:
            hi = i - 1
        else:
            lo = i + 1

import statistics
tests = [([1, 3], [2]), ([1, 2], [3, 4]), ([1, 5, 9], [2, 3, 4, 6, 7])]
for a, b in tests:
    got = median_two(a, b)
    exp = statistics.median(sorted(a + b))
    print(a, b, "-> median", got, "ok:", got == exp)

[1, 3] [2] -> median 2.0 ok: True
[1, 2] [3, 4] -> median 2.5 ok: True
[1, 5, 9] [2, 3, 4, 6, 7] -> median 4.5 ok: True

pythondef get_skyline(buildings):
    if not buildings:
        return []
    if len(buildings) == 1:
        l, r, h = buildings[0]
        return [(l, h), (r, 0)]
    mid = len(buildings) // 2
    left = get_skyline(buildings[:mid])
    right = get_skyline(buildings[mid:])
    return merge_skyline(left, right)

def merge_skyline(left, right):
    i = j = 0
    h1 = h2 = 0
    result = []
    while i < len(left) and j < len(right):
        if left[i][0] < right[j][0]:
            x, h1 = left[i]; i += 1
        elif left[i][0] > right[j][0]:
            x, h2 = right[j]; j += 1
        else:
            x, h1 = left[i]; h2 = right[j][1]; i += 1; j += 1
        cur = max(h1, h2)
        if not result or result[-1][1] != cur:
            result.append((x, cur))
    result.extend(left[i:])
    result.extend(right[j:])
    return result

buildings = [(2, 9, 10), (3, 7, 15), (5, 12, 12), (15, 20, 10), (19, 24, 8)]
print(get_skyline(buildings))

[(2, 10), (3, 15), (7, 12), (12, 0), (15, 10), (20, 8), (24, 0)]