Divide and conquer
Split problems into independent sub-problems, recurse, combine — understand the pattern in merge sort, binary search, and quickselect, with an intuition for the Master Theorem.
- Describe divide-and-conquer (split into independent sub-problems, recurse, combine)
- Identify the pattern in merge sort, binary search, and quickselect
- Understand the Master Theorem intuitively
Divide and conquer solves a problem by:
- Dividing the input into two or more smaller sub-problems.
- Conquering each sub-problem recursively (base case when the input is trivially small).
- Combining the sub-problem results into the answer for the original problem.
The key requirement — not shared by DP — is that the sub-problems are independent. No sub-problem's solution depends on another's. This is what allows them to be solved in any order and makes parallelism natural.
Three canonical examples
Merge sort. Divide the array in half, sort each half recursively, then merge the two sorted halves. The merge step is the work that happens after the recursion, and it takes O(n). Recurrence: T(n) = 2T(n/2) + O(n) → O(n log n).
Binary search. Divide the search range in half, compare the midpoint, and discard the half that cannot contain the target. No combining step needed — the answer comes directly from the chosen sub-problem. Recurrence: T(n) = T(n/2) + O(1) → O(log n).
Quickselect. Find the kth smallest element. Partition around a pivot (like quicksort), but only recurse into the side that contains the kth position. Average O(n); worst case O(n²) with bad pivots.
The Master Theorem — intuition
Many divide-and-conquer algorithms have recurrences of the form:
T(n) = a · T(n/b) + O(n^d)a= number of sub-problemsb= factor by which input shrinksd= exponent in the "combine" step cost
The dominant term depends on the balance between the branching factor and the combine cost:
| Condition | Complexity | Example |
|---|---|---|
| log_b(a) > d | O(n^(log_b a)) | Sub-problems dominate |
| log_b(a) = d | O(n^d · log n) | Balance — extra log factor |
| log_b(a) < d | O(n^d) | Combine step dominates |
For merge sort: a=2, b=2, d=1. log_2(2) = 1 = d → balanced case → O(n log n). For binary search: a=1, b=2, d=0. log_2(1) = 0 = d → O(log n).
You do not need to memorise the full Master Theorem statement. The intuition is enough: if sub-problems multiply faster than the input shrinks, the recursion tree dominates. If the combine step is expensive relative to splitting, the combine dominates. If they balance, you get an extra log factor.
Divide and conquer vs DP
Both involve recursion and overlapping structure. The distinction:
- Divide and conquer — sub-problems are independent; each is solved once.
- DP — sub-problems overlap; memoisation or tabulation avoids redundant work.
When you implement merge sort, the two halves never share elements. When you
implement Fibonacci naively, fib(4) is computed independently inside both
fib(5) and fib(6) — that overlap is what makes memoisation pay off.
Where to go next
Next: backtracking — a systematic search pattern that builds a solution incrementally and undoes choices that lead to dead ends. It applies whenever you need to enumerate or find a combination, permutation, or placement.