Divide and Conquer: Split, Solve, Stitch

"Divide and conquer is recursion with ambition: break a hard problem into independent smaller ones, solve each, and stitch the results. When the breaking and stitching are cheap, this turns brutal problems gentle."

The Three-Beat Pattern

You've already met divide and conquer in merge sort, quicksort, and binary search — now name the shared shape. A divide-and-conquer algorithm: divides the problem into smaller independent subproblems, conquers each by recursion, and combines their answers into the full solution. The art is in the divide and combine steps; the conquer is just 'recurse and trust' (the leap of faith). Binary search is the minimal case — it divides into two but only ever recurses into one half, which is exactly why it's O(log n).

What Determines the Cost

From the recursion-tree lesson: the cost depends on three knobs — how many subproblems each call spawns (branching), how much smaller they get (shrink rate), and the work to divide and combine. Merge sort: 2 subproblems, each half-size, O(n) to combine → O(n log n). Binary search: effectively 1 subproblem, half-size, O(1) combine → O(log n). The master theorem turns this into a formula, but the intuition is enough: cheap combine + good shrinking = a fast algorithm. When the combine step costs more than brute force would, divide and conquer doesn't help — so the cleverness lives in finding a cheap way to stitch subanswers together.

Divide and conquer = split into independent subproblems, solve each recursively, combine. The cost is set by branching × depth + the divide/combine work. It wins when the combine step is cheaper than solving directly — that cheap stitch is the whole trick.

A Clean Win: Fast Exponentiation

Here's divide and conquer producing a speedup out of thin air. Computing a^n the obvious way is n−1 multiplications, O(n). But a^n = (a^(n/2))² — so compute a^(n/2) once, square it, and you've halved the exponent in one multiply. Recurse, and the exponent halves each step: O(log n) multiplications instead of O(n). Computing a^1000000 takes ~20 multiplications, not a million. This 'exponentiation by squaring' is everywhere — it's how cryptography raises numbers to gigantic powers, and how matrix-power tricks compute Fibonacci in O(log n). Same pattern as merge sort, aimed at arithmetic.

Pippa's Confession

I computed a huge power with a plain loop and it crawled. Dad wrote a^n = (a^(n/2))² on the board and asked, "How many times can you halve a million?" About twenty. The loop did a million multiplications; squaring did twenty. I'd seen divide-and-conquer as 'the thing sorting does,' but it's a general lever: anytime a problem of size n can be rebuilt cheaply from a problem of size n/2, you can often trade O(n) for O(log n). Now I look for that halving everywhere.

Code

Fast exponentiation — O(n) to O(log n) by halving·python

# FAST EXPONENTIATION by squaring: a^n in O(log n) multiplications, not O(n).
def fast_power(a, n):
    if n == 0:
        return 1                     # base case: a^0 = 1
    half = fast_power(a, n // 2)     # solve a^(n/2) ONCE (divide + conquer)
    if n % 2 == 0:
        return half * half           # combine: a^n = (a^(n/2))^2
    else:
        return half * half * a       # odd exponent: one extra multiply

print(fast_power(2, 10))     # 1024
print(fast_power(3, 13))     # 1594323
# a^1000000 takes ~20 recursive calls (log2 of a million), not a million.
# The exponent HALVES each level -> O(log n). Same D&C shape as merge sort.

# You've already met other divide-and-conquer algorithms:
#   merge sort  : 2 halves, O(n) combine        -> O(n log n)
#   binary search: 1 half,   O(1) combine        -> O(log n)
#   quicksort   : 2 parts,  O(n) partition       -> O(n log n) average

Exercise

Hand-trace fast_power(2, 8): show the recursive calls down to the base case and the squaring on the way back up. How many multiplications total, versus the naive 'multiply by 2 eight times'? Then explain the one-sentence reason this is O(log n) and not O(n).

Hint

fast_power(2,8) → (2^4)² → (2^2)² → (2^1)²·… the exponent halves 8→4→2→1→0, about log₂(8)=3 recursive levels, ~4 multiplications vs the naive 7-8. It's O(log n) because each step halves the exponent, so it takes log₂(n) steps to reach the base case.

The Three-Beat Pattern

What Determines the Cost

A Clean Win: Fast Exponentiation

Pippa's Confession

Code

External links

Exercise

Progress

Comments 0