Divide & Conquer in Action — Algorithms Course

What you'll learn

Divide and conquer produces some of the most elegant algorithms in computing. Three classics show its range: computing huge powers in O(log n), multiplying big numbers faster than the schoolbook method, and finding the two closest points among thousands.

By the end you'll be able to:

Compute xⁿ in O(log n) with fast exponentiation
Explain how Karatsuba beats O(n²) multiplication
Sketch the O(n log n) closest-pair algorithm

Fast exponentiation

Computing xⁿ by multiplying x together n times is O(n). But xⁿ = (x^{n/2})², so we can halve the exponent each step — O(log n) multiplications. Watch 3¹³ resolve in five calls instead of thirteen:

Fast exponentiation of 3¹³

power(3, 13)

Call stack

power(3, 13)

13 is odd

1/10Compute 3¹³. Recurse on half the exponent.

Each call halves the exponent, so the depth is log n — then results square back up.

In code

Language

power.py

def power(x, n):
    if n == 0:
        return 1
    half = power(x, n // 2)         # one recursive call
    if n % 2 == 0:
        return half * half          # x^n = (x^(n/2))^2
    return x * half * half          # odd: one extra factor of x

Tip

This exponentiation by squaring is everywhere: modular exponentiation in cryptography (xⁿ mod m), raising a matrix to a power to jump ahead in a linear recurrence, and more. Add mod m at each multiply and you can compute enormous powers without overflow.

Karatsuba multiplication

Multiplying two n-digit numbers the schoolbook way is O(n²). Karatsuba splits each number in half and — cleverly — uses only three multiplications of half-size numbers instead of four, by reusing a sum. Its recurrence is T(n) = 3·T(n/2) + O(n), which the Master Theorem solves to O(n^{log₂3}) ≈ O(n¹·⁵⁸⁵) — a real speedup for very large integers.

Karatsuba's saving

x·y = (a·2^{n/2} + b)(c·2^{n/2} + d)

naive: ac, ad, bc, bd → 4 multiplies

Karatsuba: ac, bd, and (a+b)(c+d) → 3 multiplies

since ad + bc = (a+b)(c+d) − ac − bd

Closest pair of points

Given n points, find the two closest. Checking all pairs is O(n²). Divide and conquer does it in O(n log n): split the points by a vertical line, recursively find the closest pair in each half, then — the clever part — check only the points within a thin strip around the dividing line, where at most a constant number can be close enough to matter.

Key idea

The strip trick is the whole insight: after solving both halves, a crossing pair closer than the best-so-far d must lie within distance d of the line, and each point needs comparing to only ~6 neighbors. That keeps the combine step linear.

Recap & quick check

Key takeaways

Fast exponentiation computes xⁿ in O(log n) by squaring: xⁿ = (x^(n/2))².
It powers modular exponentiation and matrix-power tricks.
Karatsuba multiplies n-digit numbers in ~O(n^1.585) using 3 half-size multiplies, not 4.
Closest pair is O(n log n) via divide and conquer plus the strip trick.
Each recurrence is read off instantly with the Master Theorem.

Quick check

1. How many multiplications does fast exponentiation use for xⁿ?

2. Karatsuba's recurrence is T(n) = 3T(n/2) + O(n). Its complexity is:

3. What makes the closest-pair combine step efficient?

4. xⁿ = (x^(n/2))² is used because:

Divide and conquer splits problems apart. The next paradigm builds a solution greedily, one choice at a time. Next up: Module 13 — The Greedy Paradigm.