Divide & Conquer
A three-step pattern that turns hard problems into smaller copies of themselves — and the reasoning behind why it works so efficiently.
What you'll learn
- The three-step pattern — divide, conquer, combine — and when each step matters
- Recurrence relations: how T(n)=a·T(n/b)+f(n) describes recursive work
- Plain-English Master Theorem intuition without heavy math
- Why divide & conquer maps directly onto parallel systems like MapReduce and Spark
Before you start
Divide and conquer is not a single algorithm — it is a design pattern. It solves a problem by breaking it into smaller versions of the same problem, solving each one, and assembling the results. Most of the fastest algorithms you already know follow this pattern.
The three-step pattern
Every divide-and-conquer algorithm has three phases:
- Divide — split the input into two or more subproblems of the same type, each strictly smaller than the original.
- Conquer — solve each subproblem recursively. The recursion bottoms out at a base case small enough to solve directly.
- Combine — merge the subproblem solutions into a solution for the original problem.
The key insight is that the subproblems are independent — the solution to one does not depend on the solution to another. That independence is what makes the pattern so powerful.
Step through the splits and the merges:
Examples you already know
Binary search
Binary search is the simplest case: the combine step is trivial because you recurse into only one half.
- Divide: compare the target to the middle element; decide which half contains it.
- Conquer: recurse into that half.
- Combine: nothing — the recursive call returns the answer directly.
Result: O(log n). Each divide step halves the remaining work.
Merge sort
Merge sort uses all three steps non-trivially.
- Divide: split the array at the midpoint.
- Conquer: sort each half recursively.
- Combine: merge the two sorted halves in O(n).
The merge (combine) step does real work — scanning both halves linearly. That cost shapes the overall complexity: O(n log n).
A less obvious example: max subarray
Given an array of integers (possibly negative), find the contiguous subarray with the largest sum.
The divide-and-conquer approach:
- Divide: split the array at the midpoint.
- Conquer: find the max subarray in the left half and the right half recursively.
- Combine: also check subarrays that cross the midpoint — these cannot be found by either recursive call alone. The crossing maximum is computed in O(n) by expanding outward from the midpoint.
The max of the three candidates (left, right, crossing) is the answer. This gives O(n log n), better than the naive O(n²) approach.
Fast exponentiation
Computing x to the power n naively requires n multiplications. Divide and conquer cuts that to O(log n) by halving the exponent at each step.
The observation: if n is even, xⁿ = (x^(n/2))². If n is odd, xⁿ = x · x^(n−1). Each call reduces n by roughly half. You get the same answer after only log₂ n multiplications instead of n.
The playground below makes the comparison concrete.
At n = 5000 the fast version uses roughly 17 multiplications (each halving of the exponent is one step, plus a few extra for odd steps); the naive version uses 5000. That factor grows with n because the speedup is O(n) vs O(log n).
A glimpse at Karatsuba multiplication
Long multiplication of two n-digit numbers takes O(n²) digit operations. Karatsuba (1960) observed that you can multiply two 2-digit numbers using only three single-digit multiplications instead of four, by reusing an intermediate product. Applied recursively, this drops the complexity to roughly O(n^1.585). It is the same divide-and-conquer idea: split each number at the midpoint, recurse on smaller pieces, and combine cleverly to save work. Modern arbitrary-precision arithmetic libraries use it or its descendants.
Recurrence relations
Divide-and-conquer algorithms spawn recursive calls, and their complexity is expressed as a recurrence — an equation that defines T(n) (the cost on an input of size n) in terms of T on smaller inputs:
T(n) = a · T(n/b) + f(n)Read this as: to solve a problem of size n, you make a recursive calls each on a subproblem of size n/b, and do f(n) additional work to divide and combine.
| Algorithm | a | b | f(n) | Result |
|---|---|---|---|---|
| Binary search | 1 | 2 | O(1) | O(log n) |
| Merge sort | 2 | 2 | O(n) | O(n log n) |
| Fast exponentiation | 1 | 2 | O(1) | O(log n) |
| Max subarray | 2 | 2 | O(n) | O(n log n) |
Master Theorem intuition
The Master Theorem gives a closed-form answer for T(n) = a·T(n/b) + f(n). You do not need to memorise the formula — just understand the intuition.
The question is: where does most of the work happen?
Think of the recursion as a tree. At the root you do f(n) work. At the next level you have a nodes each doing f(n/b) work. This continues until you reach the base cases (the leaves), of which there are a^(log_b n) = n^(log_b a).
There are three outcomes:
- Leaves dominate (the recursive calls do proportionally more work than the split/combine step): T(n) = O(n^(log_b a)). This happens when f(n) grows slower than n^(log_b a).
- Every level does equal work (f(n) and the subproblem cost grow at the same rate): T(n) = O(n^(log_b a) · log n). Merge sort falls here: f(n) = n and n^(log_2 2) = n — equal, so you pick up an extra log factor.
- Root dominates (the split/combine step does proportionally more work than all recursive calls combined): T(n) = O(f(n)).
For merge sort: a=2, b=2, so n^(log_b a) = n^1 = n. f(n) = n. They match — every level of the recursion tree contributes the same O(n) merge work, across log n levels, giving O(n log n).
For binary search: a=1, b=2, so n^(log_2 1) = n^0 = 1. f(n) = O(1). They match — every level does O(1) work, across log n levels, giving O(log n).
Quick check
Quick check
Practice this in an interview
All questionsAt each step of a recursive walk through the input, you make a binary choice: include the current element or skip it. Recording the current path at every node of the recursion tree (not just the leaves) collects all 2^n subsets. A `start` index prevents duplicates by ensuring elements are only considered left-to-right.
Use backtracking with a running total. At each step, try adding a candidate to the current path. If the total equals the target, record the path. If it exceeds the target, prune. Passing the same start index (not i+1) back into the recursion allows unlimited reuse of the same element.
At each recursion level, swap one of the remaining (unused) elements into the current position, recurse to fill the rest, then swap back to restore the state. Alternatively, track a 'used' set and build the permutation in a separate path list. The result is all n! orderings.
Make two passes: a left pass where each position accumulates the product of everything to its left, then a right pass (using a rolling variable) that multiplies in everything to its right. The two passes together give the complete product-of-all-others in O(n) time and O(1) extra space (excluding output).