Karatsuba Multiplication and Toom-Cook Multiplication both name "the
Master Theorem" directly in their own Complexity sections — the tool that turns a
divide-and-conquer recurrence into a closed-form running time without re-deriving a recursion
tree or summing a geometric series by hand every time. This page is that tool, built standalone
rather than folded into either page: a live calculator, the formal three-case statement, and six
recurrences already proven elsewhere on this site, from a trivial a=1 case up
through two that land on a non-integer exponent.
Every divide-and-conquer recurrence the theorem covers has the shape
T(n) = a·T(n/b) + Θ(nc): a subproblems, each of size
n/b, plus a combine step that costs Θ(nc). Set the three
numbers below — by hand, or load one of the six real recurrences from this site — and see which
case applies and what it resolves to.
Any divide-and-conquer algorithm that splits a size-n problem into
a independent subproblems of size n/b each, then spends
f(n) combining their results, has a running time described by
T(n) = a·T(n/b) + f(n). Across logb n levels of recursion,
the pure cost of the recursive calls themselves (ignoring f entirely) comes out to
Θ(nlogb a) — that single exponent is the one number the whole
theorem turns on. Compare it against f(n) and exactly one of three cases applies:
f(n) is polynomially
smaller than nlogb a (not just smaller — smaller by
a factor of nε for some ε > 0), the recursive calls'
own cost swamps the combine step and T(n) = Θ(nlogb a), the
combine step's own cost disappearing from the final bound entirely.f(n) = Θ(nlogb a)
exactly, every one of the Θ(log n) levels contributes the same order of cost, and
T(n) = Θ(nlogb a log n) — the extra log n factor
is literally "that many equal-cost levels," nothing more exotic.f(n) is polynomially
larger than nlogb a, and a technical
regularity condition holds (a·f(n/b) ≤ c·f(n) for some constant
c < 1 and all large enough n — see Pitfalls below), the top level's
own combine cost already dominates everything underneath it, and
T(n) = Θ(f(n)).None of this requires knowing anything about what the algorithm computes — only the
shape of its recursion. That's both the theorem's whole value (one five-minute classification
instead of a fresh recursion-tree argument per algorithm) and its whole limit: a recurrence whose
subproblem count or size isn't a fixed a/b doesn't fit the shape at all,
see below.
Every row below is checked against that page's own Complexity section, not assumed from the
algorithm's name — see each page's own text for the full derivation of its a,
b, and f(n).
| entry | a | b | f(n) | logb a | case | bound |
|---|---|---|---|---|---|---|
| Binary Search | 1 | 2 | Θ(1) | 0 | 2 | Θ(log n) |
| Merge Sort | 2 | 2 | Θ(n) | 1 | 2 | Θ(n log n) |
| Closest Pair of Points | 2 | 2 | Θ(n) | 1 | 2 | Θ(n log n) |
| Divide-and-Conquer Convex Hull | 2 | 2 | Θ(n) | 1 | 2 | Θ(n log n) |
| Karatsuba Multiplication | 3 | 2 | Θ(n) | log₂3 ≈ 1.585 | 1 | Θ(nlog₂3) ≈ Θ(n1.585) |
| Toom-Cook Multiplication | 5 | 3 | Θ(n) | log₃5 ≈ 1.465 | 1 | Θ(nlog₃5) ≈ Θ(n1.465) |
Three different pairs of (a, b), three different outcomes. Merge Sort, Closest
Pair of Points, and Divide-and-Conquer Convex Hull all share the identical
T(n) = 2T(n/2) + Θ(n) shape — two subproblems, each half the size, linear combine —
and land on the identical Θ(n log n) bound, even though the three algorithms sort
numbers, find a nearest pair of points, and build a convex hull respectively. Karatsuba trades one
extra subproblem for a slightly smaller split factor (a=3 against Merge Sort's
a=2, same b=2) and the exponent jumps from a clean 1 to an
irrational log₂3 — there's no reason to expect a tidy number once a
isn't a power of b. Toom-Cook pushes further in the opposite direction, more
subproblems (5) but each shrinking by more (b=3 instead of
2), landing on a smaller exponent than Karatsuba's despite more
subproblems — proof that "more subproblems" alone says nothing about the final bound without
weighing it against how much each one shrinks.
Quicksort's average-case O(n log n) looks
superficially identical to Merge Sort's — same recursion depth, same per-level work — but its own
Complexity section reasons about it differently, "a good pivot splits the range roughly in half,"
not a fixed T(n) = 2T(n/2) + O(n). That phrasing is doing real work: Quicksort's
split is data-dependent, not a fixed fraction of n on every call the way
Merge Sort's literal half-and-half split is. There's no constant b to plug into the
theorem — a different random pivot gives a different, uneven split every time, and the
O(n log n) figure is really an argument about the expected depth staying
logarithmic across many unevenly-split calls, not a Master Theorem classification. Quickhull's own Complexity section makes exactly this
connection explicit, reasoning about its own average-case bound "by analogy to Quicksort" rather
than invoking the theorem — the same farthest-point step that makes Quickhull fast on well-behaved
input makes its split size data-dependent too, for the identical reason. Any time a recursive
algorithm's branch count or split sizes depend on the data rather than being fixed in
advance, the Master Theorem's T(n) = aT(n/b) + f(n) shape doesn't apply at all — not
"applies loosely," genuinely doesn't describe the recursion.
The Case 2 boundary has to match exactly, not just "closely." A combine cost
that's Θ(nlogb a) divided by even a single log factor is
already outside all three cases. The classic example: T(n) = 2T(n/2) + n/log n has
a=2, b=2, so logb a = 1 — but n/log n is
neither O(n1-ε) (Case 1 needs a genuine polynomial gap, and dividing by
log n isn't one) nor Θ(n logk n) for any k ≥ 0
(Case 2's extended form only allows non-negative log exponents, and this is effectively
k = -1) nor Ω(n^{1+ε}) (Case 3 needs a genuine polynomial excess the
other way). The calculator above can't even express this input — it only accepts a pure
Θ(nc) combine cost — which is the point: the moment f(n)
isn't a clean polynomial, the basic theorem can go silent. This particular recurrence does have an
answer, just not from this theorem: summing the recursion tree directly, level i has
2i subproblems of size n/2i, each costing
(n/2i) / log(n/2i) = (n/2i)/(log n − i), for a
per-level total of n/(log n − i); summed over i = 0 to
log n − 1 that's n · (1/log n + 1/(log n − 1) + … + 1/1) = n · Hlog n
≈ n ln(log n) — Θ(n log log n), a real bound the Master Theorem alone
can't produce.
Case 3's regularity condition is a separate, real requirement — it just doesn't show up
in any of the six examples above. For a pure polynomial f(n) = Θ(nc),
regularity is automatic whenever Case 3's own exponent test is satisfied: a·f(n/b) =
a·(n/b)c = (a/bc)·f(n), and c > logb a
means exactly bc > a, so the constant a/bc is
already below 1 — no separate check ever needed for polynomial f, which
is why every textbook introduction (and the calculator above) can get away with stating Case 3 as
"just" an exponent comparison. The condition exists as its own clause in the theorem's formal
statement specifically for the non-polynomial f(n) that calculator can't model —
treating "Case 3's exponent test passes" as the whole story works for every recurrence on this
page, but isn't true of the theorem in general.
logb a and loga b are not interchangeable — a plausible
typo that silently flips which case applies. Karatsuba's real numbers show the damage: the correct
log2 3 ≈ 1.585 against a combine cost of Θ(n1)
gives Case 1 and the real, verified bound Θ(n1.585) — but swap the base
and compute log3 2 ≈ 0.631 instead, and n1 now
looks larger than that (wrong) exponent, flipping the classification to Case 3 and
producing a confidently wrong Θ(n), understating Karatsuba's real cost by an entire
polynomial factor — not a rounding error, a different Big-Theta class.