Divide & Conquer
Divide & Conquer
Split, solve, combine — and when the recurrence pays off.
Divide and Conquer
▶ viz
Split a problem into independent subproblems of the same shape, solve them recursively, and combine the answers; the Master theorem tells you whether the split pays off.
depends on a, b, f(n) · O(log n) stack (balanced) space
Closest Pair of Points
Find the two closest points among n points in the plane in O(n log n) by splitting on x, recursing, and checking only a thin strip around the split line.
O(n log n) · O(n) space