Why it matters

Divide-and-conquer is often the fastest approach. Even when a linear algorithm exists, divide-and-conquer solutions often have better cache behavior or parallelize more naturally.

Advertisement

The architecture

Three steps: divide (split problem into subproblems), conquer (solve subproblems recursively), combine (merge results). Base case terminates recursion.

Master theorem: for recurrence T(n) = a T(n/b) + f(n), complexity depends on comparison of f(n) to n^(log_b a).

Divide-and-conquer skeletonDividesplit into k partsConquerrecurse eachCombinemerge resultsMaster theorem: complexity = leaves + internal work; classify by which dominates
D&C three steps + complexity.
Advertisement

How it works end to end

Mergesort: T(n) = 2 T(n/2) + O(n) → O(n log n).

Binary search: T(n) = T(n/2) + O(1) → O(log n).

Karatsuba multiplication: 3 T(n/2) + O(n) → O(n^1.58), better than schoolbook O(n²).

Strassen matrix mult: 7 T(n/2) + O(n²) → O(n^2.81), better than O(n³).