The divide-and-conquer method
The three-step template, the Master Theorem, and fast power. · 11 min read
The template
Divide and conquer solves a problem in three steps: divide it into smaller independent subproblems, conquer each by recursion, then combine their answers. Merge sort, quicksort, binary search, and fast exponentiation are all instances.
def solve(problem):
if small enough: return base_case(problem)
parts = divide(problem)
answers = [solve(p) for p in parts]
return combine(answers)Interactive visualization: Divide & conquer: branching by level — step through it frame by frame on this page.
The Master Theorem
Many D&C recurrences have the form T(n) = a·T(n/b) + f(n) — a subproblems of size n/b plus f(n) combine work. Compare f(n) with n^(log_b a):
f(n) ≪ n^(log_b a) ⟹ T(n) = Θ(n^(log_b a))— Leaves dominate (e.g. a=8,b=2).f(n) ≈ n^(log_b a) ⟹ T(n) = Θ(n^(log_b a) · log n)— Balanced — merge sort: a=2,b=2,f=n ⟹ n log n.f(n) ≫ n^(log_b a) ⟹ T(n) = Θ(f(n))— Combine dominates.
Result: T(n) = a·T(n/b) + f(n)
Fast exponentiation
xⁿ = (x^(n/2))² (times an extra x if n is odd) halves the exponent each step — O(log n) multiplications instead of n. The same squaring trick powers modular exponentiation (see Math) and matrix-power recurrences.
Practice: Fast Power (xⁿ) (Easy) — Compute xⁿ in O(log n) by squaring.
Practice: Binary Search (Easy) — Find a target in a sorted array in O(log n).