Divide and conquer
Three moves, always the same three. Divide the problem into smaller versions of itself. Conquer each one the same way. Combine the answers into an answer for the whole thing.
Below, the same three moves applied to three problems that look nothing alike: adding up an array, raising a number to a power, and sorting. The trees are almost identical. What differs is what the combining costs, and that is what decides whether any of it was worth doing.
Start with total, which is the honest case where splitting gains nothing at all. Then power, where it turns twenty multiplications into 6. Then sort, which is merge sort from the previous lesson, seen as the shape it is.
1function total(a, lo, hi) {2 if (hi - lo === 1) return a[lo] // one item3 const mid = (lo + hi) >> 14 const left = total(a, lo, mid) // divide5 const right = total(a, mid, hi)6 return left + right // combine7}
The split
each node divides until a piece answers itself
One problem, about to be cut in half. Then each half in half, until a piece is small enough to answer without thinking.
The three moves, why the tree stays shallow, and when splitting buys nothing.
The three moves
Watch any of the three run and the pattern is the same. A node appears and immediately splits, without solving anything. Its children split. That continues until a piece is small enough to answer outright, which is the base case from the recursion lesson wearing a different hat.
Then the answers come back up, and this is where the work happens. Nothing was computed on the way down. Every node is waiting for both its children so it can combine them, which is the same way-back-up shape the very first lesson showed with factorial.
Why the tree stays shallow
Splitting in half is what keeps these trees short. Eight items reach single items in 4 levels; a thousand items would take ten; a million, twenty. That count is log n, and it is the same log that appeared in binary search and in merge sort, for the same reason: you can only halve a number so many times.
So the cost of a divide and conquer algorithm is almost always how many levels multiplied by what one level costs. The levels are nearly always log n. The interesting part is the other factor.
When it buys nothing
Run total and count. Adding eight numbers by splitting costs eight additions, which is exactly what adding them left to right costs. The tree is prettier and the work is identical.
This matters more than the success stories. Divide and conquer is not a speed-up; it is a way of organising a problem. It only becomes a speed-up when combining two solved halves is genuinely cheaper than solving the whole from scratch.
When it buys everything
Now power. Computing 2 to the twentieth by multiplying twenty times costs twenty multiplications. By splitting, it costs 6, because 2 to the twentieth is simply the square of 2 to the tenth. Every level halves what is left to do.
And sort. Sorting a whole array by comparing every pair is quadratic. Merging two already-sorted halves is linear, because you only ever look at their two front values. Linear work at each of log n levels is O(n log n), and that is the entire reason merge sort beats bubble sort.
Reading the recurrence without the theorem
The master theorem answers this formally, but the intuition is available without it. Compare two quantities: how much work the leaves do in total, and how much work the top level does.
- Leaves dominate. There are many small pieces and combining is cheap. The total is set by the bottom of the tree.
- Levels balance. Every level costs about the same, so the total is one level's work times the number of levels. Merge sort is this case: n per level, log n levels.
- The root dominates. Splitting and combining are expensive enough that the first call outweighs everything below it, and the recursion barely matters.
Nearly every algorithm you meet is the middle case, which is why O(n log n) turns up so often that it starts to look like a law of nature rather than an arithmetic coincidence.
Where the splits are uneven
All three variants here split exactly in half, which is the friendly case. Quicksort does not: it splits wherever the pivot happens to land. An even split gives log n levels and O(n log n); a pivot that is always the smallest value gives n levels and O(n²).
The shape is identical. Only the balance changed. This is worth holding on to, because “it is divide and conquer” says nothing about the cost on its own.
The famous ones that beat the obvious bound
Some divide and conquer algorithms are famous precisely because they reduce the number of subproblems rather than their size.
Multiplying two n-digit numbers the way you were taught at school is O(n²). Karatsuba's method splits each number in half and observes that the four multiplications this seems to need can be done with three, giving about O(n^1.585). Strassen did the same to matrix multiplication, turning eight subproblems into seven.
Both are the same trick: the win came from the a in the recurrence, not the b. Splitting differently would not have helped; splitting into fewer pieces did.
The costs that do not show in the tree
Merge sort needs somewhere to merge into, so it costs O(n) extra memory on top of the array. The tree itself costs stack frames, O(log n) of them when the splits are even and O(n) when they are not, which is the stack-overflow lesson arriving from a new direction.
There is also a constant nobody writes down: every split is a function call, and below a certain size the calls cost more than the work they organise. That is why real implementations stop dividing at about sixteen elements and finish with insertion sort.
Where else the shape appears
Once you can see it, it is everywhere. Binary search is divide and conquer with one subproblem and no combining. The fast Fourier transform is divide and conquer on a polynomial. So is finding the closest pair of points in a plane, the median in linear time, and git bisect over a history of commits.
Parallelism is the modern reason it matters. Independent subproblems can run on different cores, because a divide and conquer split produces pieces that do not need to talk to each other until the combine step. Most of what a multi-core machine does with a large job has this shape underneath it.
Three questions
Pick an answer before you open one. Being wrong here is the useful part, and it is the whole reason to answer rather than read.
A problem of 1,024 items is split in half, then each half in half, until each piece holds one item. How many levels of splitting is that?
Adding up 8 numbers by splitting the array in half costs 8 additions, exactly what adding them left to right costs. So why split at all?
Raising 2 to the power of 20 by multiplying twenty times costs twenty steps. By squaring instead, the tree is only 6 levels deep. Where did the work go?
Problems
Work them before opening the answers. Reading a solution feels like learning and is not.
Name the three moves
function maximum(a, lo, hi) {
if (hi - lo === 1) return a[lo]
const mid = (lo + hi) >> 1
const left = maximum(a, lo, mid)
const right = maximum(a, mid, hi)
return left > right ? left : right
}Show the answer →Hide the answer
Divide: the two recursive calls on each half.
Conquer: each call solving its own half.
Combine: the final comparison of the two answers.The combine step is one comparison, which is constant work. Constant work at each of log n levels, with n leaves, still comes to O(n): the same as just scanning the array. Another case where the shape buys nothing.
Solve the recurrence by eye
T(n) = 2·T(n / 2) + n
How many levels, what does each level cost,
and what is the total?Show the answer →Hide the answer
log n levels. Each level costs n in total.
So O(n log n).Each level has twice as many pieces, each half the size, so the work per level stays at n. That balance is what makes this the most common shape in the whole subject.
Count the multiplications
Compute 3^16 by repeated squaring.
How many multiplications, against doing it
the direct way?Show the answer →Hide the answer
5 by squaring, against 15 directly.
3² = 9, 3⁴ = 81, 3⁸, 3¹⁶ — four squarings,
found by halving 16 down to 1.Each squaring doubles the exponent, so reaching 16 takes log2(16) = 4 steps. This is the same halving as binary search, run in reverse.
When the split goes wrong
A divide and conquer algorithm splits its input
into one piece of size 1 and one of size n-1,
doing linear work to combine.
What is the cost?Show the answer →Hide the answer
T(n) = T(n-1) + n → O(n²)The tree is n levels deep instead of log n, so the halving never happens. This is exactly what a bad quicksort pivot does, and the reason an unbalanced split destroys the advantage entirely.
Fewer pieces, not smaller ones
Multiplying two n-digit numbers by splitting each
in half seems to need four multiplications of
half-sized numbers:
T(n) = 4·T(n / 2) + n
That is O(n²), no better than long multiplication.
Karatsuba gets it to three. What does that change?Show the answer →Hide the answer
T(n) = 3·T(n / 2) + n → about O(n^1.585)The size of the subproblems did not change and neither did the combining. Only the number of them did, from four to three, and that alone moves the exponent. When a divide and conquer algorithm is famous, this is usually why.
What gets asked, and what a good answer sounds like
Say these out loud rather than reading them. The gap between knowing something and being able to say it is the thing interviews measure.
+What is divide and conquer?
Breaking a problem into smaller versions of itself, solving those the same way, and combining their answers. The cost is usually the number of levels, which is log n when you halve, multiplied by what one level costs.
+When does it actually help?
Only when combining two solved halves is cheaper than solving the whole from scratch. Merging two sorted halves is linear where sorting the whole is quadratic, so it helps enormously. Adding up an array gains nothing, because addition has no shortcut.
+Walk me through why merge sort is O(n log n).
Halving until each piece is one item gives log n levels. Merging at each level touches every element once, so each level costs n. Multiply them. As a recurrence that is T(n) = 2T(n/2) + n.
+What breaks it?
Uneven splits. If one side always gets almost everything, the depth becomes n instead of log n and the cost collapses to quadratic. That is exactly what a badly chosen quicksort pivot does, and why production implementations choose a pivot carefully or cap the recursion depth.
+Is it always recursive?
Not necessarily. Merge sort has a bottom-up form that merges runs of one, then two, then four, with a loop and no recursion at all. The decomposition is the idea; recursion is just the most natural way to write it down, and it costs stack frames for the privilege.
Know someone stuck on this? Send it to them.
A classmate, a study group, someone learning this on their own at midnight. The link opens the lesson set up exactly as you have it, the same function and the same number, and runs from the first step so they watch the whole thing build rather than landing in the middle of it.
Also in this course
Sorting: why O(n log n) beats O(n²)
Merge sort counted comparison by comparison. This lesson shows the shape underneath it.
Start there →