Skip to content

Divide and Conquer

Breaking a problem into independent subproblems of the same type, solving recursively, and combining results often achieves logarithmic depth even when total work remains substantial.

Tension Addressed

Simplicity vs. Optimality

Recognizable As

Recursive decomposition where subproblem sizes shrink geometrically; Master Theorem applies; parallelism opportunity at each level.

Canonical Sources

Karatsuba multiplication, 1962; Cooley-Tukey FFT, 1965; CLRS, Introduction to Algorithms, Chapter 4

Transfers To

Parallel computing (task decomposition), distributed systems (MapReduce), database query plans, image processing

The power lies in converting O(n^2) naive approaches to O(n log n) or better by limiting interaction between subproblems.