Breaking problems into subproblems. Merge sort, quicksort.
Quick unlock - significant prerequisite investment but simple final step. Verify prerequisites first.
Some problems feel too big to solve in one shot—but surprisingly easy if you cut them into clean pieces, solve each piece the same way, and then stitch the answers back together. Divide and conquer is that idea made precise, and it powers classic fast algorithms like merge sort and quicksort.
Divide and conquer solves a problem by (1) splitting it into smaller subproblems, (2) solving each subproblem recursively, and (3) combining the results. When the split is balanced, you often get fast runtimes like T(n) = 2T(n/2) + O(n) ⇒ O(n log n). Merge sort is the canonical example; quicksort is similar but combines “for free” and pays in the partition step.
Divide and conquer is an algorithm design pattern:
1) Decompose (Divide): Break the original problem of size n into smaller subproblems (often of size about n/2).
2) Conquer: Solve each subproblem—typically by calling the same algorithm recursively.
3) Combine: Assemble the subproblem solutions into a solution for the original problem.
Many problems have two key properties:
If those hold, you can trade one “hard” problem of size n for several “easier” ones of size n/b. If the work to combine is not too expensive, the total work can drop dramatically.
Imagine a problem is a tangled rope. Trying to untangle it all at once is frustrating. Divide and conquer says: cut it into segments, untangle each segment with the same technique, then tie the segments back together.
Divide and conquer algorithms naturally form a recursion tree:
If you split into a constant number of subproblems each time, and each split reduces size by a constant factor, the depth of the tree is about log₂ n.
Here’s a language-agnostic skeleton:
The key design choices are:
You already know recursion, but not every recursive algorithm is divide and conquer.
A practical rule of thumb:
This difference is often the difference between O(n log n) and O(n²) (or between O(log n) and O(n)).
The “divide” step is not just a structural decision—it largely determines performance.
Suppose you split a problem of size n into subproblems with sizes:
Even if the combine step is similar, the recursion depth changes dramatically.
If each level halves the input size, then after k levels you’re at size n/2ᵏ. You stop when n/2ᵏ ≈ 1.
Solve for k:
n/2ᵏ ≈ 1
⇒ 2ᵏ ≈ n
⇒ k ≈ log₂ n
So you get about log₂ n levels.
If each step reduces n by 1, then you need about n steps to reach the base case. That’s depth O(n).
Divide and conquer costs are commonly written as a recurrence:
T(n) = aT(n/b) + f(n)
Where:
A famous example is merge sort:
T(n) = 2T(n/2) + O(n)
Let’s build intuition before formal rules.
For merge sort:
Total combine work per level ≈ O(n), and there are ≈ log₂ n levels.
So total ≈ O(n log n).
Consider:
T(n) = 2T(n/2) + cn
Expand one step:
T(n) = 2[2T(n/4) + c(n/2)] + cn
= 4T(n/4) + 2c(n/2) + cn
= 4T(n/4) + cn + cn
= 4T(n/4) + 2cn
Expand again:
T(n) = 4[2T(n/8) + c(n/4)] + 2cn
= 8T(n/8) + 4c(n/4) + 2cn
= 8T(n/8) + cn + 2cn
= 8T(n/8) + 3cn
After k expansions:
T(n) = 2ᵏ T(n/2ᵏ) + kcn
Stop when n/2ᵏ = 1 ⇒ 2ᵏ = n ⇒ k = log₂ n.
Then:
T(n) = nT(1) + cn log₂ n
If T(1) is constant:
T(n) = O(n) + O(n log n) = O(n log n)
Even with a beautiful recurrence, real implementations often stop recursion early.
Example: in merge sort, you might stop when subarray length ≤ 32 and use insertion sort.
Why?
This doesn’t change asymptotic complexity, but it often improves actual performance.
Divide and conquer works best when subproblems are mostly independent.
When subproblems overlap heavily, divide and conquer alone may recompute work. That’s where dynamic programming can enter—but that’s a different node.
“Combine” is where divide and conquer either wins big or quietly loses its advantage.
Even if you split into smaller pieces, if you recombine in a costly way you can erase the benefit.
A useful way to think:
The art is to keep combine cheap enough that shrinking n dominates.
| Pattern | Example | Combine cost | Notes |
|---|---|---|---|
| Explicit merge | merge sort | O(n) | Must merge two sorted lists; linear and predictable |
| Implicit combine | quicksort | O(1) “combine” | The work is mostly in partition; after partition, concatenation is conceptually trivial |
Suppose you have two sorted arrays:
You can merge them in O(n) time by walking two pointers i and j:
Each element is moved exactly once → linear time.
The reason this is so powerful is subtle:
So the cost per level doesn’t blow up.
Quicksort does something slightly different:
1) Partition around a pivot p so that:
2) Recursively sort left and right
3) Combine by placing: sorted(left), then pivot, then sorted(right)
Combine is just concatenation, which is O(1) conceptually (or O(n) depending on in-place vs out-of-place details), but the key is: the main linear work is in partitioning, not merging.
So quicksort’s recurrence is commonly:
T(n) = T(k) + T(n−k−1) + O(n)
where k is the number of elements less than pivot.
Because quicksort’s split depends on pivot choice, you can get:
Merge sort, in contrast, always splits in half regardless of input:
T(n) = 2T(n/2) + O(n) ⇒ O(n log n) always
So there’s a stability-vs-typical-speed trade:
| Algorithm | Typical time | Worst-case time | Extra memory | Stability |
|---|---|---|---|---|
| Merge sort | O(n log n) | O(n log n) | O(n) (array version) | Stable |
| Quicksort | O(n log n) average | O(n²) | O(log n) stack (in-place) | Not stable by default |
In other divide and conquer problems, combine might be:
A famous example (not required here, but instructive): maximum subarray can be done with divide and conquer by combining left max, right max, and crossing max. Combine takes linear time unless you maintain extra boundary sums.
When inventing or analyzing a divide and conquer algorithm, ask:
1) What exact information must each subproblem return to make combine cheap?
2) Can I avoid recomputing work in combine?
3) Does combine touch every element at every level (→ likely O(n log n))?
4) Is the split guaranteed balanced, or does input affect it?
Those questions often predict runtime before any formal solving.
This section ties the pattern to two flagship algorithms and shows what “divide, conquer, combine” looks like concretely.
Sorting is a common subroutine. Many simple sorts (like insertion sort) are O(n²) in the worst case. Merge sort achieves O(n log n) deterministically by leaning hard on divide and conquer.
Split the array A into two halves:
Recursively merge sort each half.
Merge the two sorted halves with the linear two-pointer merge.
Let f(n) be merge cost: f(n) = cn.
T(n) = 2T(n/2) + cn
⇒ T(n) = O(n log n)
Merge sort can be stable: if L[i] == R[j], take from L first, preserving original relative order.
This matters when sorting records by multiple keys.
Quicksort is often the fastest comparison sort in practice due to:
But its performance depends on getting good splits.
Choose a pivot p. Rearrange the array so:
This partition step is O(n).
Recursively quicksort the left and right parts.
No merge step needed; the array is already partitioned. Conceptually:
sorted(left) + [p] + sorted(right)
Average case (random pivot or randomized input):
E[T(n)] = O(n log n)
Worst case (already sorted + poor pivot rule like “first element”):
T(n) = T(n−1) + cn
Show the sum expansion:
T(n) = T(n−1) + cn
= T(n−2) + c(n−1) + cn
= ...
= T(1) + c(2 + 3 + ... + n)
Use arithmetic series:
∑_{k=2}^{n} k = (n(n+1)/2) − 1
So:
T(n) = O(n²)
Randomly choosing the pivot (or shuffling the array first) makes worst-case behavior extremely unlikely, giving strong practical performance.
| Situation | Prefer | Reason |
|---|---|---|
| Need guaranteed O(n log n) | Merge sort | Worst-case safe |
| Need stability | Merge sort | Stable by design |
| Tight memory, in-place desired | Quicksort | O(log n) stack typical |
| Average performance is priority | Quicksort | Often faster constants |
Even if you only remember merge sort and quicksort, the bigger skill is: recognizing when a problem can be split into mostly independent subproblems and recombined cheaply.
Assume n is a power of 2, and T(1) = 1. Find a closed form (up to Θ(·)) and explain the intuition.
Start with the recurrence:
T(n) = 2T(n/2) + n
Expand one level:
T(n) = 2[2T(n/4) + (n/2)] + n
= 4T(n/4) + n + n
= 4T(n/4) + 2n
Expand a second level:
T(n) = 4[2T(n/8) + (n/4)] + 2n
= 8T(n/8) + n + 2n
= 8T(n/8) + 3n
After k expansions, the pattern is:
T(n) = 2ᵏ T(n/2ᵏ) + kn
Stop expanding at the base case when n/2ᵏ = 1:
2ᵏ = n
k = log₂ n
Substitute k back in:
T(n) = 2^{log₂ n} T(1) + n log₂ n
= n·1 + n log₂ n
= n + n log₂ n
= Θ(n log n)
Insight: The combine work is n per level, and there are log₂ n levels, so total work is n log n. This is the signature runtime of balanced divide-and-conquer with linear combine.
Sort A = [8, 3, 7, 4, 2, 6, 5, 1] using merge sort. Show the splits and one representative merge step in detail.
Divide repeatedly into halves:
[8, 3, 7, 4, 2, 6, 5, 1]
→ [8, 3, 7, 4] and [2, 6, 5, 1]
→ [8, 3] [7, 4] and [2, 6] [5, 1]
→ [8] [3] [7] [4] [2] [6] [5] [1]
Conquer (base cases): arrays of length 1 are already sorted:
[8], [3], [7], [4], [2], [6], [5], [1]
Combine: merge pairs:
merge([8],[3]) = [3,8]
merge([7],[4]) = [4,7]
merge([2],[6]) = [2,6]
merge([5],[1]) = [1,5]
Combine: merge the results:
merge([3,8],[4,7])
Result: [3,4,7,8]
merge([2,6],[1,5])
Result: [1,2,5,6]
Final combine:
merge([3,4,7,8],[1,2,5,6])
Result: [1,2,3,4,5,6,7,8]
Insight: Merge sort’s power comes from the fact that merging is linear and happens over log₂ n levels. Every element participates in one merge per level, giving Θ(n log n) time.
Run one partition-based step on A = [1, 2, 3, 4, 5]. Compare choosing pivot = 1 (worst-ish) vs pivot = 3 (balanced). Use this to write the recurrence shape.
If pivot p = 1:
Partition result is:
left = []
pivot = [1]
right = [2,3,4,5]
So the recursive sizes are 0 and 4.
Recurrence shape:
T(5) = T(0) + T(4) + O(5)
More generally (for sorted input and always-pick-first):
T(n) = T(n−1) + O(n)
If pivot p = 3:
Partition result is:
left = [1,2]
pivot = [3]
right = [4,5]
Recursive sizes are 2 and 2.
Recurrence shape:
T(5) = T(2) + T(2) + O(5)
More generally (balanced splits):
T(n) = 2T(n/2) + O(n)
Relate to asymptotics:
Balanced: 2T(n/2)+O(n) ⇒ O(n log n)
Unbalanced: T(n−1)+O(n) ⇒ O(n²)
Insight: Quicksort’s combine is essentially trivial, but its divide step (partition) must produce reasonably balanced subproblems to achieve O(n log n). Pivot strategy is therefore an algorithmic design decision, not an implementation detail.
Divide and conquer = Divide into smaller subproblems, Conquer them recursively, then Combine their answers.
Balanced splits typically give recursion depth ≈ log₂ n; unbalanced splits can give depth ≈ n.
Recurrences capture the cost: T(n) = aT(n/b) + f(n). For many classic algorithms, f(n) is linear, leading to O(n log n).
Merge sort: always balanced split, linear merge combine ⇒ Θ(n log n) worst-case, stable, usually needs O(n) extra memory.
Quicksort: partition is linear; combine is trivial; average Θ(n log n) but worst-case Θ(n²) with poor pivots.
A good combine step often requires deciding what information subproblems return so recombination is cheap.
Divide and conquer works best when subproblems are independent; heavy overlap suggests dynamic programming instead.
Assuming any recursive algorithm is divide and conquer; true D&C typically splits into multiple smaller subproblems and benefits from factor-size reduction.
Ignoring the combine cost: splitting is not enough—if combine is too expensive, total time can degrade (even to O(n²) or worse).
For quicksort, treating pivot choice as harmless: deterministic poor pivot rules can consistently trigger worst-case behavior.
Mixing up depth and total work: log₂ n depth does not automatically mean O(log n) time; you must multiply by work per level.
You design an algorithm that splits a size-n problem into 3 subproblems of size n/2 and then spends O(n) time combining. Write the recurrence and give the asymptotic runtime.
Hint: Think about the recursion tree: how many total elements are processed per level, and how many levels are there?
Recurrence:
T(n) = 3T(n/2) + O(n).
In a recursion tree, level i has 3^i subproblems of size n/2^i. If combine per subproblem is proportional to its size, total combine per level is:
3^i · (n/2^i) = n · (3/2)^i.
This grows geometrically with i, so the bottom levels dominate.
Depth is about log₂ n, so the last level has i = log₂ n:
Total ≈ n · (3/2)^{log₂ n}.
Use a^{log_b n} = n^{log_b a}:
(3/2)^{log₂ n} = n^{log₂(3/2)}.
So total is Θ(n · n^{log₂(3/2)}) = Θ(n^{1 + log₂(3/2)}) = Θ(n^{log₂ 3}).
Therefore T(n) = Θ(n^{log₂ 3}) (about Θ(n^{1.585})).
Show that the recurrence T(n) = 2T(n/2) + n² is Θ(n²).
Hint: Compare work per level: does it stay constant like n, or change with level?
At level 0, non-recursive work is n².
At level 1, there are 2 subproblems of size n/2, each costing (n/2)², so total is:
2 · (n²/4) = n²/2.
At level 2:
4 · (n/4)² = 4 · (n²/16) = n²/4.
So level i costs n² / 2^i.
Sum over i = 0 to log₂ n:
∑_{i=0}^{log₂ n} n²/2^i ≤ ∑_{i=0}^{∞} n²/2^i = 2n².
So total is O(n²). Also the first level alone costs n², so it is Ω(n²).
Therefore T(n) = Θ(n²).
Consider quicksort with a pivot that always ends up splitting into sizes 1 and n−2 (ignoring the pivot itself). Write a recurrence and solve it to Θ(·).
Hint: This is still essentially a linear chain like T(n) = T(n−1) + O(n). Unroll it into a sum.
Recurrence:
T(n) = T(1) + T(n−2) + O(n).
Since T(1) is constant, this behaves like:
T(n) = T(n−2) + cn.
Unroll:
T(n) = T(n−2) + cn
= T(n−4) + c(n−2) + cn
= T(n−6) + c(n−4) + c(n−2) + cn
Continue until the argument reaches 1 (about n/2 steps). The sum is roughly:
cn + c(n−2) + c(n−4) + ...
This is an arithmetic series with about n/2 terms and average term about n/2, so total is Θ(n²).
Therefore T(n) = Θ(n²).