Divide and Conquer (D&C) solves a problem in three steps:
- Divide — split the input into smaller, independent subproblems.
- Conquer — solve each subproblem recursively (base cases are trivial).
- Combine — merge the subproblem solutions into the full answer.
It is the engine behind the algorithms you already visualized in the sorting studio: Merge Sort (split, sort, merge), Quick Sort (partition, sort halves), and Binary Search (halve and recurse).
D&C vs Dynamic Programming
The decisive difference is whether subproblems overlap:
| Divide & Conquer | Dynamic Programming | |
|---|---|---|
| Subproblems | Independent | Overlapping |
| Repeated work | None | Plenty without a table |
| Example | Merge Sort | Knapsack, LCS |
D&C problems usually need no table because each subproblem appears once. When the same subproblem recurs (Fibonacci recursion, LCS), you’re really doing DP and should memoize.
Analyzing D&C with Recurrences
D&C algorithms have a natural recurrence:
T(n) = a · T(n/b) + f(n)asubproblems, each of sizen/b, plusf(n)cost to divide and combine.
The Master Theorem resolves these:
f(n) = O(n^c)withc < log_b(a)→T(n) = O(n^(log_b a))f(n) = Θ(n^c)withc = log_b(a)→T(n) = O(n^c log n)f(n) = Ω(n^c)withc > log_b(a)→T(n) = O(f(n))
Worked Examples
| Algorithm | Recurrence | Result |
|---|---|---|
| Binary Search | T(n) = T(n/2) + O(1) | O(log n) |
| Merge Sort | T(n) = 2T(n/2) + O(n) | O(n log n) |
| Quick Sort (avg) | T(n) = T(k) + T(n-k) + O(n) | O(n log n) |
| Strassen’s Matrices | T(n) = 7T(n/2) + O(n²) | O(n^2.807) |
Beyond Sorting
D&C powers many non-sorting algorithms:
- Binary Search — halves the search space per step.
- Closest Pair of Points — split plane, recurse, then check the thin strip across the cut.
- Fast Fourier Transform (FFT) — splits the polynomial into even/odd terms;
O(n log n). - Strassen / Karatsuba — clever splitting beats naive matrix/multiplication costs.
- Segment Tree and BIT queries — recursively split ranges.
Practice Trajectory
Implement Merge Sort and Quick Sort by hand, then prove their recurrences with the Master Theorem. Move on to closest-pair and inversion counting (a Merge Sort variant), then to FFT and Strassen to see the “reduced subproblem count” trick that powers near-linear algorithms.