[Intermediate → Advanced] — The previous lesson showed that a divide-and-conquer recurrence has only three possible outcomes: the leaves dominate, the levels are equal, or the root dominates. The Master Theorem is those three outcomes written as a theorem, with the conditions made precise so you can apply it without drawing anything.
It is genuinely a shortcut — thirty seconds instead of five minutes. It is also the topic most likely to be misapplied, because two of its most famous-looking targets fall outside it. Knowing when it does not apply is the harder and more valuable half.
Before you start
- You can turn recursive code into , and you know what , and mean — recursion trees and recurrences.
- You can compute the work at level of a recursion tree and say which level dominates.
- You are comfortable with logarithms changing base, and with .
After this lesson you will be able to:
- Apply the theorem’s decision procedure to an unfamiliar recurrence and produce a bound.
- Explain what “polynomially larger” means and why Case 3 requires it.
- Identify the two standard recurrences the theorem cannot solve, and say precisely which condition each violates.
- Verify any verdict empirically with the doubling test.
Study route: read 1–3, then attempt the prediction in section 4 before continuing. Section 5 — where it fails — is the part worth rereading.
1. Why this exists: the same three cases, every time
Every divide-and-conquer recurrence you solved in the last lesson followed the same ritual: compute the work at level , see whether it grows, stays flat or shrinks, and pick the corresponding answer. Doing that from scratch each time is wasted effort, because the answer depends on only two numbers.
Those two numbers are:
- — the total work at the leaves, since there are of them.
- — the work at the root.
The whole theorem is: compare those two, and whichever is bigger wins. If they tie, the answer is their common value times the number of levels.
That is the idea. The precision is in what “bigger” has to mean.
Terms used in the Master Theorem
- Master Theorem: This is a rule that solves recurrences of the form by comparing against . It gives a bound — a tight one, not just an upper bound.
- The critical exponent: This is , sometimes called the watershed exponent. It is the exponent at which leaf work and root work balance. Everything in the theorem is a comparison against .
- Polynomially larger: This means larger by a factor of for some fixed . is polynomially larger than (take ). is larger than but not polynomially larger, because grows slower than for every positive , however small. This distinction is the single most important idea in the lesson.
- Polynomially smaller: The mirror image — smaller by a factor of for some fixed . Case 1 requires it.
- Regularity condition: This is the extra requirement in Case 3: for some constant and all sufficiently large . In words: the total combine work must actually shrink as you go down the tree, by a constant factor. It holds for every polynomial you will meet in practice, and exists to exclude pathological functions that oscillate.
- The gap: This is the region between the cases where the theorem says nothing — when is larger or smaller than but only by a logarithmic factor rather than a polynomial one. lives here.
2. The theorem
Stated in words first. Given a recurrence in which a problem of size is split into subproblems of size , with work to divide and combine, compare the work done at the leaves, , with the work done at the root, :
- If the leaves are polynomially more work, the leaves dominate and the total is the leaf work.
- If the two match, every level does about the same work, and the total is that amount times the number of levels — an extra factor of .
- If the root is polynomially more work and the combine work shrinks regularly down the tree, the root dominates and the total is just the root’s work.
Now the symbols. For with and :
The in Cases 1 and 3 is doing all the work. It is what makes “smaller” and “larger” mean polynomially so, and it is exactly what versus fails to satisfy.
3. The decision procedure
Follow it in order. Do not skip step 1.
- Is the recurrence even of this form? It needs — the input shrinking by a factor. If the input shrinks by a constant amount, as in , the theorem does not apply at all. Go back to the recursion tree.
- Compute the critical exponent .
- Compare with :
- smaller by a polynomial factor → Case 1, answer .
- equal, possibly times → Case 2, answer .
- larger by a polynomial factor → Case 3, answer .
- For Case 3 only, check regularity. For any it holds automatically: , and Case 3 already requires , which forces .
- If the comparison is “larger/smaller, but only by a logarithmic factor”, you are in the gap. The theorem says nothing. Draw the tree.
Worked: merge sort
. So , , .
, so . And . They match, with .
Case 2 gives . ✓
Worked: binary search
. So , , .
, so . And . They match, .
Case 2 gives . ✓
Notice that binary search is a Case 2, not a Case 1. People expect the “one branch” recurrence to be special; it is not. With the critical exponent is 0, and constant work matches exactly.
Worked: Strassen’s matrix multiplication
. So , , .
. Is polynomially smaller than ? Yes — take .
Case 1 gives .
This is the entire reason Strassen’s algorithm is famous. Naive matrix multiplication is ; the same combine work with seven subproblems instead of eight drops the exponent to 2.807. The lab measures it: the ratio of measured work to holds steady at 2.31–2.32 across — a constant, which is what claims.
4. The comparison that catches people
Predict before reading on. . The critical exponent is , and is clearly bigger than . So it is Case 3, giving . Find the error in that reasoning.
There are two errors, and they compound.
Error one: Case 3 requires to be polynomially larger, and is not. Case 3 needs for some fixed . Here . For any , however tiny, eventually falls behind — grows slower than . So no valid exists, and Case 3 does not apply.
Error two: the conclusion is wrong too. Falling in the gap does not mean the answer is whatever Case 3 would have said. Drawing the tree: level has nodes of size , so the level work is
Summing over to gives .
The true answer is , not — a whole logarithmic factor larger than the wrong reasoning predicted. The lab confirms it: the measured doubling ratio (2.552, 2.486, 2.435, 2.393) tracks the prediction (2.612, 2.531, 2.469, 2.420), not the 2.2-and-falling that would give.
This recurrence can in fact be handled by Case 2, since with , giving — the same answer. The trap is not that the recurrence is unsolvable; it is that reaching for Case 3 because ” looks bigger” gives the wrong answer. Check which case actually applies before applying one.
5. Where the theorem genuinely fails
Three situations, in decreasing order of how often they come up.
1. The input shrinks by subtraction, not division
is not of the form . There is no . The theorem is silent.
The tree is still easy: depth , work doubling per level, so . The lab prints the node counts — 2,047 at , 2,097,151 at .
This is the case that matters most in interviews, because — naive Fibonacci — looks superficially like a divide-and-conquer recurrence and is nothing of the sort.
2. is in the gap
Covered in section 4. The signature is a ratio that is a power of , or anything else sub-polynomial. Sometimes Case 2’s extended form rescues it; sometimes nothing does, and you draw the tree.
3. The subproblems are not all the same size
— the recurrence for quicksort with a guaranteed 1:2 split — has two different subproblem sizes. The theorem assumes identical subproblems of size .
The tree still works: every level does work until branches start bottoming out, and the longest path has length , giving . The useful takeaway is that even a lopsided constant-ratio split gives — quicksort does not need good pivots, only pivots that are not catastrophically bad.
There is a generalisation, the Akra–Bazzi method, that handles unequal splits. It is worth knowing the name and not worth memorising the formula.
6. Worked example — complete runnable lab
Save as master_theorem.py. Standard library only. It classifies each recurrence by the theorem, then checks the verdict against measured work by doubling — so the theorem is being tested, not just recited.
"""Apply the Master Theorem, then check its verdict against measured work.
Run: python3 master_theorem.py
"""
import math
from collections import defaultdict
def measure(a, b, f, n):
"""Total work for T(n) = a*T(n/b) + f(n), summed over the whole tree."""
by_level = defaultdict(float)
def rec(size, level):
by_level[level] += f(size)
if size <= 1:
return
for _ in range(a):
rec(size / b, level + 1)
rec(n, 0)
return sum(by_level.values())
def classify(a, b, f_exp, f_log=0):
"""Classify T(n) = a*T(n/b) + n^f_exp * (log n)^f_log by the Master Theorem.
Returns (case, description, growth-rate function).
"""
crit = math.log(a) / math.log(b) # log_b(a): the 'leaves' exponent
if f_exp < crit - 1e-12:
return (1, f"f(n) grows slower than n^{crit:.3f} -> LEAVES win",
lambda n: n ** crit)
if abs(f_exp - crit) < 1e-12:
if f_log < 0:
return (None, "f/n^crit decreases -> Master Theorem does NOT apply", None)
return (2, f"f(n) matches n^{crit:.3f} -> ALL LEVELS equal",
lambda n: (n ** crit) * (math.log2(n) ** (f_log + 1)))
return (3, f"f(n) grows faster than n^{crit:.3f} -> ROOT wins",
lambda n: (n ** f_exp) * (math.log2(n) ** f_log))
def report(a, b, f, f_exp, f_log, label, name):
case, why, growth = classify(a, b, f_exp, f_log)
crit = math.log(a) / math.log(b)
print(f"\n {label} [{name}]")
print(f" a={a}, b={b}, log_b(a) = {crit:.4f}, f(n) = {describe(f_exp, f_log)}")
print(f" Case {case}: {why}")
if growth is None:
print(" -> fall back to the recursion tree")
return
print(f" verdict: T(n) = Theta({formula(case, crit, f_exp, f_log)})")
print(" n | measured work | measured ratio | predicted ratio")
prev = None
for n in (128, 256, 512, 1024, 2048):
w = measure(a, b, f, n)
mr = f"{w/prev:>14.3f}" if prev else f"{'-':>14}"
pr = f"{growth(n)/growth(n/2):>15.3f}" if prev else f"{'-':>15}"
print(f" {n:>7} | {w:>17,.0f} | {mr} | {pr}")
prev = w
def describe(e, l):
base = "1" if e == 0 else ("n" if e == 1 else f"n^{e}")
if l == 0:
return base
return f"{base} * log(n)" if l == 1 else f"{base} * log(n)^{l}"
def formula(case, crit, f_exp, f_log):
if case == 1:
return f"n^{crit:.3f}"
if case == 2:
return f"n^{crit:.3f} * log(n)^{f_log + 1}"
return describe(f_exp, f_log)
def main():
print("=" * 78)
print("THE MASTER THEOREM: T(n) = a*T(n/b) + f(n)")
print("Compare f(n) against n^(log_b a). Whichever is bigger, wins.")
print("=" * 78)
print("\n### CASE 1 -- f(n) is smaller: the leaves dominate")
report(2, 2, lambda s: 1.0, 0, 0, "T(n) = 2T(n/2) + 1", "tree traversal / heapify")
report(4, 2, lambda s: s, 1, 0, "T(n) = 4T(n/2) + n", "naive matrix-ish")
print("\n\n### CASE 2 -- f(n) matches: every level does equal work")
report(2, 2, lambda s: s, 1, 0, "T(n) = 2T(n/2) + n", "merge sort")
report(1, 2, lambda s: 1.0, 0, 0, "T(n) = T(n/2) + 1", "binary search")
print("\n\n### CASE 3 -- f(n) is bigger: the root dominates")
report(2, 2, lambda s: s * s, 2, 0, "T(n) = 2T(n/2) + n^2", "root-heavy combine")
report(1, 3, lambda s: s, 1, 0, "T(n) = T(n/3) + n", "shrink-and-scan")
print("\n\n### THE FAMOUS NEAR-MISSES")
print("\n (a) T(n) = 7T(n/2) + n^2 [Strassen matrix multiplication]")
crit = math.log2(7)
print(f" log_2(7) = {crit:.4f}, and f(n) = n^2 with 2 < {crit:.4f}")
print(f" Case 1 -> Theta(n^{crit:.4f}), which beats the naive n^3")
for n in (128, 256, 512):
w = measure(7, 2, lambda s: s * s, n)
print(f" n={n:>5} measured={w:>18,.0f} n^2.807={n**crit:>18,.0f}"
f" ratio={w/(n**crit):>6.2f}")
print("\n (b) T(n) = 2T(n/2) + n*log(n) [Master Theorem does NOT apply]")
print(" f(n) = n log n is bigger than n^1, but NOT polynomially bigger:")
print(" the ratio f(n)/n^1 = log n grows slower than any n^epsilon.")
print(" Case 3 needs f(n) = Omega(n^(crit+eps)) for some eps > 0. It fails.")
print(" The recursion tree still works: n*log(n) per level shrinking slowly,")
print(" log n levels -> Theta(n * log(n)^2).")
print(" n | measured work | measured ratio | n*log2(n)^2 ratio")
prev = None
for n in (128, 256, 512, 1024, 2048):
w = measure(2, 2, lambda s: s * math.log2(s) if s > 1 else 1.0, n)
pred = lambda m: m * (math.log2(m) ** 2)
mr = f"{w/prev:>14.3f}" if prev else f"{'-':>14}"
pr = f"{pred(n)/pred(n/2):>17.3f}" if prev else f"{'-':>17}"
print(f" {n:>7} | {w:>17,.0f} | {mr} | {pr}")
prev = w
print("\n (c) T(n) = 2T(n-1) + 1 [not a Master Theorem shape at all]")
print(" The theorem requires the input to shrink by a FACTOR (n/b),")
print(" not by a constant AMOUNT (n-c). Use the recursion tree:")
print(" depth n, work doubling per level -> Theta(2^n).")
for n in (10, 15, 20):
total = 2 ** (n + 1) - 1
print(f" n={n:>3} nodes = 2^(n+1)-1 = {total:>12,}")
print("\n\n### THE DECISION PROCEDURE, IN ORDER")
print(" 1. Is it of the form a*T(n/b) + f(n), with a >= 1 and b > 1?")
print(" If the input shrinks by subtraction, STOP -- use the recursion tree.")
print(" 2. Compute crit = log_b(a).")
print(" 3. Compare f(n) to n^crit:")
print(" f smaller by a polynomial factor -> Case 1: Theta(n^crit)")
print(" f equal (up to log^k) -> Case 2: Theta(n^crit * log^(k+1) n)")
print(" f bigger by a polynomial factor -> Case 3: Theta(f(n))")
print(" 4. For Case 3, check regularity: a*f(n/b) <= c*f(n) for some c < 1.")
print(" It holds for every polynomial f you are likely to meet.")
print(" 5. If the comparison is 'bigger but only by a log factor', the theorem")
print(" does NOT apply. Go back to the tree.")
if __name__ == "__main__":
main()Expected output
Generated by running the file above:
==============================================================================
THE MASTER THEOREM: T(n) = a*T(n/b) + f(n)
Compare f(n) against n^(log_b a). Whichever is bigger, wins.
==============================================================================
### CASE 1 -- f(n) is smaller: the leaves dominate
T(n) = 2T(n/2) + 1 [tree traversal / heapify]
a=2, b=2, log_b(a) = 1.0000, f(n) = 1
Case 1: f(n) grows slower than n^1.000 -> LEAVES win
verdict: T(n) = Theta(n^1.000)
n | measured work | measured ratio | predicted ratio
128 | 255 | - | -
256 | 511 | 2.004 | 2.000
512 | 1,023 | 2.002 | 2.000
1024 | 2,047 | 2.001 | 2.000
2048 | 4,095 | 2.000 | 2.000
T(n) = 4T(n/2) + n [naive matrix-ish]
a=4, b=2, log_b(a) = 2.0000, f(n) = n
Case 1: f(n) grows slower than n^2.000 -> LEAVES win
verdict: T(n) = Theta(n^2.000)
n | measured work | measured ratio | predicted ratio
128 | 32,640 | - | -
256 | 130,816 | 4.008 | 4.000
512 | 523,776 | 4.004 | 4.000
1024 | 2,096,128 | 4.002 | 4.000
2048 | 8,386,560 | 4.001 | 4.000
### CASE 2 -- f(n) matches: every level does equal work
T(n) = 2T(n/2) + n [merge sort]
a=2, b=2, log_b(a) = 1.0000, f(n) = n
Case 2: f(n) matches n^1.000 -> ALL LEVELS equal
verdict: T(n) = Theta(n^1.000 * log(n)^1)
n | measured work | measured ratio | predicted ratio
128 | 1,024 | - | -
256 | 2,304 | 2.250 | 2.286
512 | 5,120 | 2.222 | 2.250
1024 | 11,264 | 2.200 | 2.222
2048 | 24,576 | 2.182 | 2.200
T(n) = T(n/2) + 1 [binary search]
a=1, b=2, log_b(a) = 0.0000, f(n) = 1
Case 2: f(n) matches n^0.000 -> ALL LEVELS equal
verdict: T(n) = Theta(n^0.000 * log(n)^1)
n | measured work | measured ratio | predicted ratio
128 | 8 | - | -
256 | 9 | 1.125 | 1.143
512 | 10 | 1.111 | 1.125
1024 | 11 | 1.100 | 1.111
2048 | 12 | 1.091 | 1.100
### CASE 3 -- f(n) is bigger: the root dominates
T(n) = 2T(n/2) + n^2 [root-heavy combine]
a=2, b=2, log_b(a) = 1.0000, f(n) = n^2
Case 3: f(n) grows faster than n^1.000 -> ROOT wins
verdict: T(n) = Theta(n^2)
n | measured work | measured ratio | predicted ratio
128 | 32,640 | - | -
256 | 130,816 | 4.008 | 4.000
512 | 523,776 | 4.004 | 4.000
1024 | 2,096,128 | 4.002 | 4.000
2048 | 8,386,560 | 4.001 | 4.000
T(n) = T(n/3) + n [shrink-and-scan]
a=1, b=3, log_b(a) = 0.0000, f(n) = n
Case 3: f(n) grows faster than n^0.000 -> ROOT wins
verdict: T(n) = Theta(n)
n | measured work | measured ratio | predicted ratio
128 | 192 | - | -
256 | 384 | 2.002 | 2.000
512 | 768 | 2.000 | 2.000
1024 | 1,536 | 2.001 | 2.000
2048 | 3,072 | 2.000 | 2.000
### THE FAMOUS NEAR-MISSES
(a) T(n) = 7T(n/2) + n^2 [Strassen matrix multiplication]
log_2(7) = 2.8074, and f(n) = n^2 with 2 < 2.8074
Case 1 -> Theta(n^2.8074), which beats the naive n^3
n= 128 measured= 1,899,755 n^2.807= 823,543 ratio= 2.31
n= 256 measured= 13,363,821 n^2.807= 5,764,801 ratio= 2.32
n= 512 measured= 93,808,891 n^2.807= 40,353,607 ratio= 2.32
(b) T(n) = 2T(n/2) + n*log(n) [Master Theorem does NOT apply]
f(n) = n log n is bigger than n^1, but NOT polynomially bigger:
the ratio f(n)/n^1 = log n grows slower than any n^epsilon.
Case 3 needs f(n) = Omega(n^(crit+eps)) for some eps > 0. It fails.
The recursion tree still works: n*log(n) per level shrinking slowly,
log n levels -> Theta(n * log(n)^2).
n | measured work | measured ratio | n*log2(n)^2 ratio
128 | 3,712 | - | -
256 | 9,472 | 2.552 | 2.612
512 | 23,552 | 2.486 | 2.531
1024 | 57,344 | 2.435 | 2.469
2048 | 137,216 | 2.393 | 2.420
(c) T(n) = 2T(n-1) + 1 [not a Master Theorem shape at all]
The theorem requires the input to shrink by a FACTOR (n/b),
not by a constant AMOUNT (n-c). Use the recursion tree:
depth n, work doubling per level -> Theta(2^n).
n= 10 nodes = 2^(n+1)-1 = 2,047
n= 15 nodes = 2^(n+1)-1 = 65,535
n= 20 nodes = 2^(n+1)-1 = 2,097,151
### THE DECISION PROCEDURE, IN ORDER
1. Is it of the form a*T(n/b) + f(n), with a >= 1 and b > 1?
If the input shrinks by subtraction, STOP -- use the recursion tree.
2. Compute crit = log_b(a).
3. Compare f(n) to n^crit:
f smaller by a polynomial factor -> Case 1: Theta(n^crit)
f equal (up to log^k) -> Case 2: Theta(n^crit * log^(k+1) n)
f bigger by a polynomial factor -> Case 3: Theta(f(n))
4. For Case 3, check regularity: a*f(n/b) <= c*f(n) for some c < 1.
It holds for every polynomial f you are likely to meet.
5. If the comparison is 'bigger but only by a log factor', the theorem
does NOT apply. Go back to the tree.
Reading the lab
- Every
predicted ratiocolumn comes from the theorem’s verdict; everymeasured ratiocomes from summing the actual tree. They agree to three decimal places in Cases 1 and 3, and converge in Case 2 (where the ratio approaches its limit slowly, because of the factor). - Binary search prints as Case 2 with critical exponent 0.000. That is correct and is the subtle one: with , , and constant combine work matches it.
- Near-miss (b) is the important block. The measured ratios (2.552 → 2.393) sit clearly above what would produce (which would be 2.2 and falling, as seen in the merge-sort block) and track instead. The wrong answer and the right answer are distinguishable from measurements alone, which is the practical reason to care about the gap.
7. Common pitfalls and traps
- Applying it to a subtractive recurrence. is not . If you “apply” the theorem anyway you will get instead of the correct .
- Treating “bigger” as enough for Case 3. It must be polynomially bigger. against is the standard counterexample, and it is standard because it is the one everybody gets wrong.
- Forgetting the regularity condition exists. In practice it always holds for polynomial , but you should be able to say what it is and why it is needed — it is a natural follow-up question after you quote Case 3.
- Getting backwards. It is , not . For it is , not . A quick sanity check: more subproblems should give a larger exponent.
- Assuming Case 2 always contributes exactly one . With the answer carries . For you get , as in section 4.
- Using it on unequal splits. has two subproblem sizes and is outside the theorem. The tree gives .
- Quoting when the recurrence only gives . The Master Theorem yields tight bounds when its conditions hold. If your is only an upper bound — because you wrote for the combine step without knowing it is exactly linear — then your conclusion is an upper bound too.
- Forgetting the theorem describes the recurrence, not the algorithm. If you derived the recurrence wrongly — miscounting subproblems, or including recursive work in — the theorem will faithfully give you the right answer to the wrong question.
8. Check your understanding
-
. Which case, and what is the answer?
Answer
$\log_2 8 = 3$, and $f(n) = n^2$ is polynomially smaller than $n^3$ (take $\varepsilon = 1$). Case 1, so $\Theta(n^3)$. This is naive block matrix multiplication — eight subproblems of half the size, quadratic combine — and it is exactly the algorithm Strassen improves on by getting $a$ from 8 down to 7. -
. Which case?
Answer
None of them. The critical exponent is 1, and $f(n) = n/\log n$ is smaller than $n$ — but only by a logarithmic factor, not a polynomial one, so Case 1 does not apply. It is also not $\Theta(n\log^k n)$ for any $k \ge 0$, so Case 2 does not apply either. This is the gap on the low side. (The tree gives $\Theta(n\log\log n)$, which is a genuinely surprising answer and the reason the gap is worth respecting.) -
Why does appear inside a logarithm while is its base, rather than the other way round?
Answer
Because the tree has $\log_b n$ levels — each level divides the size by $b$ — and the node count multiplies by $a$ at each. So the leaf count is $a^{\log_b n}$, and rewriting that with the identity $a^{\log_b n} = n^{\log_b a}$ puts $a$ inside the log with base $b$. The shrink factor sets the depth; the branching factor sets the growth per level. -
You derive for an algorithm. What is it, and can you name a real one with that shape?
Answer
$\log_3 3 = 1$, $f(n) = n$ matches $n^1$, so Case 2 gives $\Theta(n\log n)$. A three-way merge sort has exactly this shape — and note it is the same complexity as two-way merge sort. Increasing the split factor does not help asymptotically, because the extra branching is exactly cancelled by the reduced depth. -
A colleague applies Case 3 to and reports . The measured doubling ratios are 2.55, 2.49, 2.44. Is the answer right, and how do the numbers tell you?
Answer
Wrong. A genuine $\Theta(n\log n)$ produces ratios just above 2 and falling toward it — the lab's merge-sort block shows 2.25, 2.22, 2.20. Ratios around 2.4–2.55 are too high for $n\log n$ and match $n\log^2 n$, whose predicted ratios are 2.61, 2.53, 2.47. The error is applying Case 3 to a function that is larger only by a log factor rather than polynomially.
9. Practice — independent task
Write master(a, b, f_exp, f_log) that applies the theorem and returns a verdict — then prove it to yourself by measurement.
Part 1 — the classifier. Return a tuple (case, bound_string), where case is 1, 2, 3, or None for “does not apply”. Handle: ; constant; with a factor; and the gap on both sides.
Part 2 — the verifier. Write verify(a, b, f, predicted_growth, sizes) that measures actual total work at doubling sizes and reports whether the measured ratios match the predicted ones to within a tolerance you choose and justify.
Part 3 — the table. Run both over these ten recurrences and produce a single table of predicted case, predicted bound, measured ratio, and agrees?:
| # | Recurrence | # | Recurrence | |
|---|---|---|---|---|
| 1 | 6 | |||
| 2 | 7 | |||
| 3 | 8 | |||
| 4 | 9 | |||
| 5 | 10 |
Rows 9 and 10 must be reported as “theorem does not apply” or “outside the theorem’s form” — not as a number. If your classifier returns a case for either, it has a bug, and finding it is the point of including them.
Part 4 — the gap. For row 9, solve it by recursion tree by hand, then check your answer against the measurement. Then do the same for and see whether you can recover .
Edge cases: ; not an integer (try ); ; below the base case.
Done when: your classifier gets all ten rows right including the two it must refuse; every verdict it does give is confirmed by measurement within your stated tolerance; and you can state in one sentence why row 5 () and row 8 () both come out as despite landing in different cases.
Before moving on
You can apply the decision procedure to an unfamiliar recurrence, say what “polynomially larger” means and why Case 3 needs it, identify the recurrences the theorem cannot touch, and confirm any verdict by doubling the input.
Recap: for , compare with — the root’s work against the leaves’ work. Polynomially smaller gives Case 1, ; a match (possibly times ) gives Case 2, ; polynomially larger, plus regularity, gives Case 3, . The word “polynomially” is the whole trap: is larger than but not polynomially so, which puts outside Case 3 — its true answer is . The theorem does not apply at all to subtractive recurrences like , nor to unequal splits like ; for those, draw the tree. Merge sort is Case 2, binary search is Case 2 with critical exponent 0, and Strassen is Case 1 at .
Next: Divide and Conquer — the algorithm design technique these recurrences were describing all along, and how to choose , and deliberately rather than discovering them after the fact.
Related
- Recursion Trees and Recurrences — the previous lesson, and the fallback whenever the theorem does not apply
- Recursion Fundamentals — where the recurrences come from
- Divide and Conquer — the technique these recurrences describe
- Merge Sort — the canonical Case 2
- Binary Search — Case 2 with critical exponent 0
- Growth and Asymptotic Notation — what is claiming
- Discrete maths: induction and recursion — the proof of the theorem itself
- the recursion folder
Software engineering
Infrastructure & security
Computer science
Hardware & engineering