4.1Divide and conquer
The idea
Divide and conquer splits the problem into smaller copies, solves them recursively and combines the answers.
Think of it like this: Delegating: a manager splits a report among assistants and stitches their pieces together.
Why it exists
The cost always follows from a recurrence, so this connects directly to the Master theorem.
How it works
- Divide into subproblems of the same kind.
- Conquer each recursively (stop at a small base case).
- Combine the results.
- Solve the recurrence for the total cost.
Worked example: Strassen: 7 multiplications instead of 8
T(n) = 7T(n/2) + n² gives Θ(n^log₂7) = Θ(n^2.81), better than the schoolbook n³.
Now play with it
- →Use the Master theorem lab with the Strassen button.
- →Compare Karatsuba (3 subproblems) with a = 4.
| Algorithm | Recurrence | Time |
|---|---|---|
| Binary search | T(n) = T(n/2) + 1 | Θ(log n) |
| Merge sort | T(n) = 2T(n/2) + n | Θ(n log n) |
| Max and min | T(n) = 2T(n/2) + 2 | Θ(n), 3n/2 − 2 comparisons |
| Karatsuba | T(n) = 3T(n/2) + n | Θ(n^1.585) |
| Strassen | T(n) = 7T(n/2) + n² | Θ(n^2.81) |
| Closest pair of points | T(n) = 2T(n/2) + n | Θ(n log n) |
| Fast power xⁿ | T(n) = T(n/2) + 1 | Θ(log n) multiplications |
T(n) = a · T(n / b) + Θ( nk · logp n )
log_b a = 2.807 > k = 2: the leaves dominate (there are n^2.807 of them)
| level | subproblems a^i | size n / b^i (n = 1024) | work at the level |
|---|---|---|---|
| 0 | 1 | 1024 | 10,48,576 |
| 1 | 7 | 512 | 18,35,008 |
| 2 | 49 | 256 | 32,11,264 |
| 3 | 343 | 128 | 56,19,712 |
| 4 | 2401 | 64 | 98,34,496 |
| 5 | 16807 | 32 | 1,72,10,368 |
Level work shrinking down the table: root dominates (Case 3). Growing: leaves dominate (Case 1). Staying the same: Case 2, multiply by the number of levels.
Check yourself
Finding both the maximum and minimum by divide and conquer takes
Exam notes (the dense version)
Split into subproblems, solve recursively, combine. Cost comes from the recurrence T(n) = aT(n/b) + f(n). Examples: merge sort, quick sort, binary search, max and min in 3n/2 − 2 comparisons, Strassen (7 multiplications, Θ(n^2.81)), Karatsuba (3 multiplications, Θ(n^1.585)), closest pair in Θ(n log n), fast exponentiation in O(log n) multiplications.
Previous year questions: Algorithm Design: Divide & Conquer, Greedy, DP (7)
PYQs are grouped by topic, so this is the full set for Algorithm Design: Divide & Conquer, Greedy, DP; try the ones that match this subtopic. Open all 7 on the topic page.