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

For a non-negative integer exponent n, exponentiation by squaring halves n at every step, so it uses O(log n) recursive levels and a constant number of multiplications per level. a^1,000,000 needs about twenty halving levels, plus the extra multiplies required at odd exponents; it is not exactly twenty multiplications. Supporting negative exponents requires a separate reciprocal contract, including what to do with zero.

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 halving levels. The loop did a million-scale amount of work; squaring needed those levels plus the multiplies on odd steps. 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

For this implementation, n follows 8→4→2→1→0. Each positive level squares, and n=1 adds one multiplication, for five multiplications under this counting convention. The asymptotic point is O(log n) levels.

The Three-Beat Pattern

What Determines the Cost

A Clean Win: Fast Exponentiation

Pippa's Confession

Code

External links

Exercise

Progress

Comments 0