Split the problem, solve the pieces, combine the answers. It is the paradigm behind merge sort, quick sort and binary search — and the recursion tree shows exactly where the log n comes from.
Controls
array size n8
The Recursion Tree
step 0
Insight
Three phases at every level: divide into subproblems, conquer them recursively, combine the results.
T(n) = a·T(n/b) + f(n)
↑ ↑ ↑
pieces size combine
levels0
work / level0
total0
Complexity
Merge sortO(n log n)
Binary searchO(log n)
DepthO(log n)
Divide and Conquer
Break it up, solve the pieces, stitch them back — and the log n falls out of the tree depth.
Quick Context
Divide and conquer solves a problem by splitting it into smaller instances of itself, solving those recursively, and combining the results. Three phases: divide, conquer, combine.
Where log n Comes From
The recursion tree makes it obvious. Each level halves the problem size, so it takes log₂n levels to reach size 1 — that is the height of the tree.
In merge sort, every level does O(n) total work (each element is touched once during merging), and there are log n levels. Multiply: O(n log n). Raise n in the lab and watch the level count grow by exactly one each time you double.
The Master Theorem
For recurrences of the form T(n) = a·T(n/b) + f(n) — a subproblems of size n/b, plus f(n) to combine — the answer depends on which dominates:
Leaves dominate — most work at the bottom.
Balanced — equal work per level, giving the extra log factor. Merge sort sits here: T(n) = 2T(n/2) + O(n) → O(n log n).
Root dominates — the combine step is the expensive part.
Binary search is T(n) = T(n/2) + O(1): one subproblem, trivial combine — so O(log n) total. It discards half the work rather than recursing into both halves, which is why it beats merge sort's complexity.
The Combine Step Is Where the Work Lives
Dividing is usually trivial — compute a midpoint. The interesting engineering is almost always in combining.
Merge sort — merging two sorted halves is O(n) and needs O(n) scratch space.
Quick sort — inverts the pattern: it partitions before recursing, so the combine step is free. That is why it sorts in place.
Maximum subarray — the answer may straddle the midpoint, so combining must scan outward from the centre.
Why It Matters Beyond Sorting
Divide and conquer parallelises naturally — independent subproblems can run on different cores, which is why it underpins MapReduce and most parallel frameworks. It is also the pattern behind Karatsuba multiplication, the Fast Fourier Transform, and closest-pair-of-points.
Interactive Exploration Guide
Step through merge sort at n = 8. Watch the tree split down to single elements, then merge back upward.
Count the levels: 3 for n = 8. That is log₂8, and it is exactly where the log n factor comes from.
Double n to 16. The level count rises by one, not by double — logarithmic growth, visible.
Switch to binary search. Only one branch is followed at each level, so the tree is a path — O(log n) rather than O(n log n).
Compare work per level. Merge sort does O(n) at every level; binary search does O(1). That single difference produces the whole complexity gap.
Key Takeaway
Divide and conquer gets its log factor from tree depth: halving repeatedly takes log n levels. Multiply that by the work per level and you have the complexity. Recursing into every branch gives O(n log n); discarding all but one gives O(log n).
Cheat sheet
Divide and Conquer
Split the problem, solve the pieces, combine the answers. It is the paradigm behind merge sort, quick sort and binary search — and the recursion tree shows exactly where the log n comes from.