Divide and conquer and the master theorem
Read a recursion tree level by level, apply a precise master theorem, and recognize recurrences outside its scope.
On this page
The question for today
What you’ll understand
- Identify branching, shrinkage, and nonrecursive work in a recurrence.
- Apply the polynomial-gap and balanced cases with their hypotheses.
- Distinguish logarithmic tree depth from total work across all nodes.
Splitting a problem into smaller pieces saves time only when the pieces and their assembly are affordable. A recursion tree makes those costs visible: depth counts how long one chain of calls lasts, while total work sums every branch. The master theorem packages a useful family of such sums. Understanding the tree first helps you recognize when the theorem applies, which term dominates, and why an appealing logarithmic depth can coexist with a much larger running time.
A level contains many calls
Consider T(n) = aT(n/b) + f(n), with fixed integer branching a at least one, fixed b greater than one, and a constant-cost positive base case. Start with powers of b so no rounding obscures the picture. At depth j there are a to the j calls, each processing size n divided by b to the j. Their combined nonrecursive work is that count times f evaluated at the reduced size. The depth is logarithmic, but the number of calls can grow geometrically.
At the leaves there are n raised to log base b of a constant-sized instances. That exponent is the comparison scale for f. For merging two sorted halves, a and b are both two, and f is linear: each level pays proportional to n, and there are logarithmically many levels. For binary search there is only one recursive half, so a is one and each level has constant work. Naming the actual recursive calls prevents confusing these two very different trees.
Compare with the leaf exponent
One standard master theorem assumes f is asymptotically nonnegative. Write d = log base b of a. If f is O(n to the d minus epsilon) for some fixed positive epsilon, leaf work dominates and T is Theta(n to the d). If f is Theta(n to the d times log to the k of n), for fixed k at least zero, every scale contributes and T is Theta(n to the d times log to the k plus one of n). These are polynomial-gap and balanced cases, respectively.
If f is Omega(n to the d plus epsilon), a root-dominated conclusion additionally needs regularity: a f(n/b) must be at most c f(n) eventually for a constant c smaller than one. Then T is Theta(f(n)). The extra condition rules out irregular costs whose descendants remain too large compared with the root. A gap of merely log n does not satisfy a polynomial-gap condition. Select the exact theorem version before applying it; different textbook extensions cover different boundary cases.
Read what the recurrence omits
The recurrence must include splitting, combining, data copying, and any substantial local allocation. Calling two slices can cost more than calling two index ranges if the implementation copies their contents. Parallel elapsed time is a different quantity from total sequential work: independent calls may overlap, while the recurrence here adds their work. Memory analysis also differs because sequential recursion can release one child's storage before processing another. A time theorem should not silently become a space or parallel-speedup theorem.
Unequal subproblem sizes, a branching factor that changes with n, and subtracting one rather than dividing by a constant require other arguments. Expansion, induction, or a suitable more general theorem may still solve them. For typical positive polynomial tolls, floor and ceiling versions preserve the familiar orders, but that conclusion needs compatible base cases and regular growth assumptions. Testing a few small sizes is useful for finding a recurrence error; it cannot replace checking the theorem's domain and hypotheses.
Work it through
Two trees with the same depth
Compare A(n) = 4A(n/2) + n with B(n) = 2B(n/2) + n for powers of two and positive constant base costs.
Both trees have depth log₂ n, because each call halves the input size. For A, the leaf exponent is log₂ 4 = 2; the linear toll is polynomially smaller, so A(n) is Theta(n²).
For B, the leaf exponent is log₂ 2 = 1. Its linear toll matches the leaf scale, so the balanced theorem with k = 0 gives Theta(n log n).
Check the level sums directly. A pays n·2^j at depth j, so its work grows toward the leaves. B pays n at every internal depth, so summing the logarithmically many levels introduces the additional logarithm.
Equal recursion depths do not imply equal total work: four children yield quadratic work here, while two children yield n log n work.
The living notebook
Explore the model
Interactive lab · root-finding
Separate one path from a branching tree
Pause and reset, then set both controls to c = 3 and U = 4. Predict a single bracket-refinement chain with width 4 divided by 2^j after j noncollapsing steps; use Step to inspect it. For a fresh comparison, pause and reset, then set c = 3 and U = 2 and compare the initial scale. This instrument follows only the retained half at each refinement. On paper contrast its one active child with a hypothetical algorithm that solves both halves. It shows neither merge-sort branches nor a runtime benchmark.
- Midpoint after 0 refinements
- 1.5
- Bracket error bound
- 1.5
- Computed residual · x² − c
- 0.25
Bisection of x² − c on [0,U], capped at 50 iterations for floating-point resolution. The error bound is the maximum distance from the displayed midpoint to either bracket endpoint (half the width in exact arithmetic). Compensated square evaluation preserves the bracket when ordinary multiplication rounds a residual to zero. A truly exact endpoint or midpoint collapses the bracket. This is one monotone quadratic, not a general root solver. Parameter changes pause playback and recompute the model at the current elapsed time. Reset restores both parameters and returns time to zero. Playback starts paused. Adjust either parameter, then choose Play or Step.
Look forA logarithmic chain of refinements describes depth; a work recurrence must also count every child at each level.
Pause & reason
Check your understanding
Your turn
Try it yourself
Analyze T(n) = 8T(n/2) + n³ for powers of two, and explain why replacing the toll by n² changes the result. Assume a positive constant base cost.
Take a moment to make a prediction or work it out on paper. Open a hint when you need one.
Give me a hint
Compute the leaf exponent once and compare each toll with it.
Compare with the solution
The exponent log₂ 8 equals three. With the n³ toll, every internal level pays Theta(n³); summing log₂ n levels gives Theta(n³ log n). With n² instead, the toll is polynomially smaller than n³ by a factor n. Leaf work dominates, yielding Theta(n³). The branching and depth are identical in the two recurrences, but the accumulated contribution of internal levels differs.
Keep the idea
Take it with you
- Depth follows shrinkage, while total work also follows branching and local costs.
- The master theorem compares a toll with the leaf exponent under specific regularity assumptions.
- Recurrences outside equal-size fixed-ratio division need a different justified method.
Read further
Original sources and deeper explanations to follow at your own pace.
Optional progress, saved in this browser when available. Revisit any lesson at any time.
Lesson not marked complete.