Master Theorem

The master theorem is a closed-form recipe for solving divide-and-conquer recurrences of the shape T(n) = a · T(n/b) + f(n) — where a problem of size n is broken into a subproblems of size n/b, each solved recursively, and f(n) extra work is done to combine the results. Without the theorem you would draw a recursion tree, sum the per-level work, and take an asymptotic; with the theorem you compare f(n) against the watershed function n^(log_b a) and read off the answer in one of three cases. The theorem fails on roughly half of all “natural-looking” recurrences (the so-called gap cases between Cases 1–2 and 2–3, and any recurrence with unequal subproblem sizes), and the Akra–Bazzi method is the more general tool to reach for when the master theorem doesn’t apply.

1. Intuition — Where the Three Cases Come From

Every divide-and-conquer recurrence has a recursion tree. At the root you do f(n) work. At depth d there are a^d subproblems of size n / b^d, each doing f(n / b^d) work; total at that level is a^d · f(n / b^d). The recursion bottoms out at depth log_b n with a^(log_b n) = n^(log_b a) leaves, each doing Θ(1) work.

So the total work is dominated by whichever level dominates:

Leaves dominate. If f(n) shrinks fast enough as you go down the tree (small per-level work but lots of leaves), the leaf count n^(log_b a) wins. → Case 1.
All levels are equal. If f(n) is exactly on the watershed, every level contributes the same amount, and you pay that amount at every level — the answer picks up an extra log n factor. → Case 2.
Root dominates. If f(n) is heavy enough that the work shrinks geometrically as you descend, the root’s f(n) dominates the whole sum. → Case 3.

The single number that decides which level dominates is the exponent of the watershed function: log_b a. Compare f(n) to n^(log_b a) and one of the three cases applies (or, sometimes, none of them — the gap cases). That comparison is the entire master theorem.

2. The Watershed Function `n^(log_b a)` — Why That Specific Exponent?

The recursion has a children per node and the size shrinks by a factor of b per level. After d levels, the work below a node is governed by the number of leaves under it, which grows as a^d. For the whole tree, the total leaf count is a^(log_b n). By the change-of-base identity

a^(log_b n) = (b^(log_b a))^(log_b n) = b^((log_b a) · (log_b n)) = n^(log_b a)

So n^(log_b a) is, by definition, the work done at the bottom of the recursion (the leaves). Comparing f(n) (root work) to n^(log_b a) (leaf work) tells you which side of the tree dominates. Let c* := log_b a, called the critical exponent. The recipe becomes:

compute c* = log_b a,
compare f(n) to n^(c*),
read off the case.

3. Tiny Worked Example — Merge Sort

Merge Sort satisfies T(n) = 2 · T(n/2) + Θ(n), so a = 2, b = 2, f(n) = Θ(n). The critical exponent is c* = log_2 2 = 1, so the watershed is n^1 = n. The combine work f(n) = Θ(n) is exactly on the watershed. Case 2 applies, and T(n) = Θ(n^1 · log n) = Θ(n log n).

We just solved a recurrence in three lines. That’s the value of the theorem — no recursion-tree drawing, no induction, no telescoping sum.

4. The Three Cases — Formal Statement

Assume a ≥ 1, b > 1 are constants and f(n) is asymptotically positive. Let c* = log_b a. The statement below is the generalized master theorem — the form given by the Wikipedia article (Master theorem) and by CLRS 4th edition, which admits a log^k n factor in Case 2. CLRS 3rd edition (Theorem 4.1, verified against the original text) states Case 2 only for k = 0 — f(n) = Θ(n^(c*)) ⇒ T(n) = Θ(n^(c*) lg n) — and treats everything else as a gap. The difference matters and is called out explicitly below; it is the source of the most common confusion about this theorem.

Case 1 — Leaves dominate

If there exists a constant ε > 0 such that

f(n) = O( n^(c* − ε) )

then

T(n) = Θ( n^(c*) ).

Recipe. “If f(n) is polynomially smaller than the watershed (smaller by some n^ε factor), the leaves win and the answer is n^(c*).”

Case 2 — Watershed match

f(n) = Θ( n^(c*) · log^k n )    for some k ≥ 0

then

T(n) = Θ( n^(c*) · log^(k+1) n ).

Recipe. “If f(n) is on the watershed (possibly with a polylog factor), every level contributes the same amount and the answer picks up an extra log n factor.”

Which textbook does this match? The k = 0 case — f(n) = Θ(n^(c*)) ⇒ T(n) = Θ(n^(c*) lg n) — is exactly CLRS 3rd edition’s Theorem 4.1 Case 2, verified against the original (CLRS 3rd ed., §4.5). The general k ≥ 0 form (admitting a log^k n factor) is not in CLRS 3rd edition — it is the version stated by Wikipedia and by CLRS 4th edition. The master-theorem idea originates with Bentley, Blostein (née Haken), and Saxe (1980), “a unifying method” for divide-and-conquer recurrences (Wikipedia); the polylog-extended Case 2 is a later generalization, not part of that original paper. In an interview, the k = 0 form is the bare minimum every grader accepts; the k ≥ 1 form is correct only under the generalized statement, so name which one you are using.

Case 3 — Root dominates

If there exists a constant ε > 0 such that

f(n) = Ω( n^(c* + ε) )

and the regularity condition holds: there is some c < 1 and large enough n such that

a · f(n / b) ≤ c · f(n)

then

T(n) = Θ( f(n) ).

Recipe. “If f(n) is polynomially larger than the watershed and shrinks geometrically as we descend (the regularity condition), the root dominates and the answer is Θ(f(n)).”

The regularity condition is a technical requirement to keep the geometric series from misbehaving — it almost always holds for natural f(n) like polynomials, but it is not automatic and must be checked. See §8 for an example where it fails.

5. Worked Examples — One Per Case (and Variations)

5.1 Case 1 — Binary Search

Binary Search satisfies T(n) = T(n/2) + Θ(1), i.e., a = 1, b = 2, f(n) = Θ(1). Critical exponent c* = log_2 1 = 0. Watershed n^0 = 1. We compare f(n) = Θ(1) to n^0 = 1. They are the same order, not polynomially smaller — so Case 1 does not apply. Instead we hit Case 2 with k = 0: T(n) = Θ(log n). (A subtle but important diagnostic — beginners often misclassify binary search as Case 1.)

A real Case 1 example: T(n) = 4 · T(n/2) + n. Here a = 4, b = 2, so c* = log_2 4 = 2, watershed is n². The combine work f(n) = n = O(n^(2 − 1)), polynomially smaller. Case 1. Answer: T(n) = Θ(n²).

5.2 Case 2 — Merge Sort and Friends

We did T(n) = 2 · T(n/2) + Θ(n) above (Case 2, answer Θ(n log n)). The same recurrence appears in Quicksort’s average-case analysis, in Heap Sort’s BUILD-MAX-HEAP argument, and in many sweep-line divide-and-conquer geometric algorithms.

A polylog-factor example: T(n) = 2 · T(n/2) + n log n. Here c* = 1, watershed n, and f(n) = n log n = Θ(n^1 · log^1 n). This recurrence sits exactly on the fault line between the two textbook statements. Under the generalized master theorem (Wikipedia / CLRS 4th ed.), it is Case 2 with k = 1 and the answer is T(n) = Θ(n · log² n). Under CLRS 3rd edition this is a gap case — CLRS uses this very recurrence as its canonical “the master method does not apply” example, because f(n)/n^(c*) = log n is not a polynomial factor, so it falls between Case 2 and Case 3 (CLRS 3rd ed., §4.5, p. 96). Both routes that do yield an answer (the generalized theorem, or Akra–Bazzi — see §9) agree it is Θ(n log² n); the disagreement is purely about whether the 3rd-edition master theorem is allowed to be invoked. State which theorem you are using. (This recurrence arises in some divide-and-conquer DP problems.)

5.3 Case 3 — Strassen vs. Schoolbook Matrix Multiplication

Schoolbook matrix multiplication: T(n) = 8 · T(n/2) + Θ(n²). Eight half-size multiplications + n² additions. Critical exponent c* = log_2 8 = 3, watershed n³. Combine work is n² = O(n^(3−1)), polynomially smaller. Case 1. Answer: T(n) = Θ(n³) — the classic cubic running time.

Strassen’s algorithm (Strassen 1969) reduces matrix multiplication to 7 recursive multiplications instead of 8, by clever algebraic identities. Recurrence: T(n) = 7 · T(n/2) + Θ(n²). Now c* = log_2 7 ≈ 2.807, watershed n^(2.807...). Combine n² = O(n^(2.807 − 0.5)), polynomially smaller. Case 1. Answer: T(n) = Θ(n^(log_2 7)) ≈ Θ(n^2.807). Strassen’s beats schoolbook asymptotically because it pushed the leaf count below n^3.

A clean Case 3 example: T(n) = 2 · T(n/2) + n². Here c* = 1, watershed n, and f(n) = n² = Ω(n^(1+1)), polynomially larger. The regularity condition: a · f(n/b) = 2 · (n/2)² = n²/2 ≤ c · n² for any c ≥ 1/2 < 1. ✓ Case 3. Answer: T(n) = Θ(n²).

This recurrence shows up in algorithms where the combine step is more expensive than the recursion — e.g., the closest-pair-of-points algorithm if implemented naively at the merge step.

5.4 Case 1 — Karatsuba Multiplication

Karatsuba (1962) multiplies two n-digit numbers via T(n) = 3 · T(n/2) + Θ(n). Three multiplications of half-size numbers, linear addition/subtraction. c* = log_2 3 ≈ 1.585, watershed n^1.585. Combine n = O(n^(1.585 − 0.5)). Case 1. Answer: T(n) = Θ(n^(log_2 3)) ≈ Θ(n^1.585). The whole point of Karatsuba is to push the asymptotic below the schoolbook Θ(n²).

5.5 Why Floyd–Warshall Is Not a Master-Theorem Recurrence

Floyd-Warshall runs in Θ(V³) but its recurrence isn’t of the form a · T(n/b) + f(n) — it’s a triple-nested loop, not a divide-and-conquer split. The master theorem doesn’t apply. Mentioning it here only because the question “what’s T(V) = ?” sometimes confuses students into reaching for the master theorem when no D&C decomposition exists. Always check that your recurrence has the right shape first.

5.6 Many Subproblems with Tiny Combine — Searches in Trees

Binary Search Tree traversals in balanced trees give T(n) = 2 · T(n/2) + Θ(1), so c* = 1, watershed n, and f(n) = Θ(1) = O(n^(1 − 1)), polynomially smaller. Case 1. Answer: T(n) = Θ(n). Matches our intuition that visiting every node of a balanced tree of size n is linear.

6. Side-by-Side Recipe

For any T(n) = a · T(n/b) + f(n):

Compute the critical exponent c* = log_b a.
Compute the watershed n^(c*).
Compare f(n) to the watershed:
- polynomially smaller (i.e., O(n^(c* − ε)) for some ε > 0) → Case 1, T(n) = Θ(n^(c*)).
- same order (i.e., Θ(n^(c*) · log^k n) for some k ≥ 0) → Case 2, T(n) = Θ(n^(c*) · log^(k+1) n). (Only the k = 0 sub-case is in CLRS 3rd ed.; k ≥ 1 needs the generalized statement — see §4.)
- polynomially larger (i.e., Ω(n^(c* + ε))) and regularity holds → Case 3, T(n) = Θ(f(n)).

Anything else is a gap case (see §8).

7. Pseudocode — A Master-Theorem “Solver”

The theorem itself isn’t an algorithm, but interviewers sometimes ask you to programmatically classify a recurrence. Here is the recipe expressed as pseudocode for the simple polynomial case f(n) = Θ(n^k):

classify(a, b, k):
    cstar := log(a) / log(b)
    if k < cstar:                      # Case 1
        return Theta(n^cstar)
    elif k == cstar:                   # Case 2 (with no logs in f)
        return Theta(n^cstar * log n)
    else:                              # k > cstar, Case 3
        # check regularity: a * (n/b)^k <= c*n^k  iff  a/b^k < 1
        if a < b^k:
            return Theta(n^k)
        else:
            return "regularity fails — gap case 3"

The condition a < b^k is the cleanest form of the regularity condition for polynomial f: equivalent to a · (1/b)^k = a / b^k < 1, a geometric ratio less than 1.

8. Gap Cases — When the Master Theorem Doesn’t Apply

The theorem covers most “textbook” recurrences but leaves real gaps:

Gap 1–2. f(n) is asymptotically smaller than n^(c*) but not by a polynomial factor. Example: T(n) = 2 · T(n/2) + n / log n. Here c* = 1, and f(n) = n / log n is smaller than n but only by a logarithmic factor — not n^ε for any ε > 0. The master theorem says nothing. (The Akra–Bazzi method handles this; the answer is T(n) = Θ(n · log log n).)
Gap 2–3. f(n) is asymptotically larger than n^(c*) but not by a polynomial factor. CLRS 3rd edition’s own example is T(n) = 2 · T(n/2) + n · log n: here c* = 1, and f(n)/n^(c*) = log n, which is not n^ε for any ε > 0, so under the 3rd-edition theorem it falls into the gap (CLRS 3rd ed., §4.5, p. 96). The generalized theorem (Wikipedia / 4th ed.) rescues exactly this shape via Case 2 with k = 1, giving Θ(n log² n) (see §5.2). A recurrence that no polylog extension rescues — a true gap under both statements — is T(n) = 2 · T(n/2) + n · log log n, whose f(n) has neither a polynomial gap nor a clean log^k n form; Akra–Bazzi gives Θ(n log n · log log n).
Regularity-fails Case 3. Even when f(n) is polynomially larger, the regularity condition can fail. Constructed example: T(n) = T(n/2) + n · (2 + sin n). The combine work oscillates and the regularity condition a · f(n/b) ≤ c · f(n) doesn’t hold uniformly. The theorem’s Case 3 doesn’t apply; you need a more careful argument.
Unequal subproblem sizes. T(n) = T(n/3) + T(2n/3) + Θ(n) (the recurrence for “median” Quickselect partitions, or for the Ternary Search tree). The master theorem requires a single b; this has two. Use the Akra–Bazzi method or a recursion-tree argument. (Answer: Θ(n log n).)
Subtractive recurrences. T(n) = T(n − 1) + Θ(n) is Θ(n²) but is not of master-theorem form. The recurrence is “subtractive” rather than “divide and conquer”. Solve by direct summation: T(n) = Σ_{k=1..n} k = Θ(n²).

CLRS 3rd edition is explicit that these are genuine gaps, not solvable by its master theorem: “Note that the three cases do not cover all the possibilities for f(n). There is a gap between cases 1 and 2 when f(n) is smaller than n^(log_b a) but not polynomially smaller. Similarly, there is a gap between cases 2 and 3 when f(n) is larger than n^(log_b a) but not polynomially larger. If the function f(n) falls into one of these gaps, or if the regularity condition in case 3 fails to hold, you cannot use the master method to solve the recurrence” (CLRS 3rd ed., §4.5, p. 95). The Wikipedia article lists the same inadmissible shapes and points to Akra–Bazzi for them (Wikipedia). Be wary of tutorial sites that paper over these gaps with informal recipes; for a true gap, use Akra–Bazzi (next section) or a direct recursion-tree analysis.

9. Akra–Bazzi — The General Hammer for Unbalanced Splits

The Akra–Bazzi method (Akra & Bazzi 1998 paper, with the version most commonly presented being Leighton’s 1996 manuscript) generalises the master theorem to recurrences of the form

T(n) = Σ_{i=1..k}  a_i · T(b_i · n + h_i(n))  +  g(n)

where each a_i ≥ 0, each 0 < b_i < 1, the h_i are small perturbations (|h_i(n)| ≤ n / log²n), and g(n) is positive and polynomially bounded. The solution is

T(n) = Θ( n^p · ( 1 + ∫_1^n  g(u) / u^(p+1)  du ) )

where p is the unique solution to Σ_{i=1..k} a_i · b_i^p = 1.

For the master theorem’s single-subproblem case T(n) = a · T(n/b) + g(n), Akra–Bazzi degenerates: the equation a · (1/b)^p = 1 gives p = log_b a = c*. The integral then handles all three cases (and the gap cases) uniformly. Akra–Bazzi is strictly more general than the master theorem and reduces to it on the same inputs.

Worked example. T(n) = T(n/3) + T(2n/3) + Θ(n). We need (1/3)^p + (2/3)^p = 1. By inspection p = 1 works (1/3 + 2/3 = 1). The integral becomes ∫_1^n u / u² du = ln n. So T(n) = Θ( n · (1 + ln n) ) = Θ(n log n). The same answer you’d get from a careful recursion tree, but mechanical.

The cost of generality is that Akra–Bazzi requires solving the characteristic equation and computing an integral — usually fine, occasionally unpleasant.

10. Common Recurrences — A Reference Table

Recurrence	Source	`c* = log_b a`	Case	Answer
`T(n) = T(n/2) + Θ(1)`	Binary Search	0	2 (k=0)	`Θ(log n)`
`T(n) = 2T(n/2) + Θ(1)`	Tree traversal	1	1	`Θ(n)`
`T(n) = 2T(n/2) + Θ(n)`	Merge Sort, Quicksort avg	1	2 (k=0)	`Θ(n log n)`
`T(n) = 2T(n/2) + Θ(n log n)`	Some D&C DP	1	2 (k=1)†	`Θ(n log² n)`
`T(n) = 2T(n/2) + Θ(n²)`	Heavy combine	1	3	`Θ(n²)`
`T(n) = 4T(n/2) + Θ(n)`	Naive integer mult	2	1	`Θ(n²)`
`T(n) = 4T(n/2) + Θ(n²)`	Naive matrix subroutines	2	2 (k=0)	`Θ(n² log n)`
`T(n) = 3T(n/2) + Θ(n)`	Karatsuba multiplication	log₂3 ≈ 1.585	1	`Θ(n^1.585)`
`T(n) = 7T(n/2) + Θ(n²)`	Strassen matrix multiplication	log₂7 ≈ 2.807	1	`Θ(n^2.807)`
`T(n) = 8T(n/2) + Θ(n²)`	Schoolbook matrix mult	3	1	`Θ(n³)`
`T(n) = T(n/2) + Θ(n)`	Linear D&C scan	0	3	`Θ(n)`
`T(n) = T(n/3) + T(2n/3) + Θ(n)`	Unequal split	n/a	Akra–Bazzi	`Θ(n log n)`
`T(n) = T(n−1) + Θ(n)`	Subtractive	n/a	not D&C	`Θ(n²)`

† Case 2 with k = 1 only under the generalized master theorem (Wikipedia / CLRS 4th ed.); under CLRS 3rd ed. this is a gap-2-3 case and you must reach for Akra–Bazzi instead (both give Θ(n log² n)). See §5.2.

11. Pitfalls

Misreading the recurrence shape. The theorem requires exactly a · T(n/b) + f(n). T(n) = T(n−1) + ... is not divide-and-conquer; you need iteration or substitution. T(n) = T(√n) + ... is also outside the theorem’s scope (Akra–Bazzi handles some of these via change of variables).
Forgetting the “polynomial” gap. Cases 1 and 3 require f(n) to differ from the watershed by a polynomial factor — an n^ε for some constant ε > 0. A merely-logarithmic gap (f(n) = n / log n vs. n) is not polynomial and falls into the gap case.
Skipping the regularity check in Case 3. Most natural f(n) (polynomials, polylogs) satisfy regularity, but exotic combine functions may not. Always verify a · f(n/b) ≤ c · f(n) for some c < 1.
Confusing the watershed n^(log_b a) with (log n)^a or similar. The exponent is log_b a, not log a, not log_b n. Check the formula carefully — getting it wrong gives nonsense answers.
Mixing up a and b. a is the number of subproblems; b is the factor by which the size shrinks. T(n) = 2 · T(n/3) + ... has a=2, b=3, not the other way round.
Calling Case 2 “T(n) = Θ(n log n)” by reflex. Case 2 gives Θ(n^(c*) · log n) — only Θ(n log n) when c* = 1. Don’t pattern-match without checking the exponent.
Treating Θ as O. The theorem’s conclusion is a Θ (tight) bound, not just an upper bound. The hypotheses also use Θ for Case 2; weakening them to O voids the conclusion.
Trying to apply the master theorem to non-D&C recurrences. Loop-based recurrences (e.g., T(n) = T(n−1) + n for naive recursive sum) are not in scope.
Forgetting the regularity-fails subcase of Case 3. A polynomial gap on f(n) is necessary but not sufficient for Case 3 — regularity is the second hypothesis.

12. Diagram — The Recursion Tree and the Watershed

flowchart TD
  R["root: f(n) work, 1 node"]
  L1["depth 1: a · f(n/b) work, a nodes"]
  L2["depth 2: a² · f(n/b²) work, a² nodes"]
  Ld["..."]
  Lk["depth log_b n: a^(log_b n) = n^(log_b a) leaves, Θ(1) work each"]

  R --> L1 --> L2 --> Ld --> Lk

  C1["Case 1: leaves dominate<br/>f(n) = O(n^(log_b a − ε))<br/>T(n) = Θ(n^(log_b a))"]
  C2["Case 2: every level equal<br/>f(n) = Θ(n^(log_b a) · log^k n)<br/>T(n) = Θ(n^(log_b a) · log^(k+1) n)"]
  C3["Case 3: root dominates<br/>f(n) = Ω(n^(log_b a + ε)) + regularity<br/>T(n) = Θ(f(n))"]

  Lk -.-> C1
  Ld -.-> C2
  R -.-> C3

What this diagram shows. The left chain is the recursion tree: at depth d, there are a^d subproblems, each of size n/b^d, contributing a^d · f(n/b^d) total work. The leaves at depth log_b n contribute n^(log_b a) total work. The right side groups the three cases by which level dominates the sum: Case 1 → leaves, Case 2 → every level equally, Case 3 → root. The watershed function n^(log_b a) is the dividing line; comparing f(n) to it tells you which side of the tree (top vs. bottom) drives the total.

13. Common Interview Problems

Problem	Recurrence	Master Theorem Result
Sort an array efficiently (Merge Sort)	`T(n) = 2T(n/2) + Θ(n)`	Case 2 → `Θ(n log n)`
Find the median (Median of Medians)	`T(n) = T(n/5) + T(7n/10) + Θ(n)`	Akra–Bazzi → `Θ(n)`
Multiply two large integers (Karatsuba)	`T(n) = 3T(n/2) + Θ(n)`	Case 1 → `Θ(n^log₂3)`
Multiply two matrices (Strassen)	`T(n) = 7T(n/2) + Θ(n²)`	Case 1 → `Θ(n^log₂7)`
Find closest pair of points (planar D&C)	`T(n) = 2T(n/2) + Θ(n)`	Case 2 → `Θ(n log n)`
Search a sorted array (Binary Search)	`T(n) = T(n/2) + Θ(1)`	Case 2, k=0 → `Θ(log n)`
Tournament max/min	`T(n) = 2T(n/2) + Θ(1)`	Case 1 → `Θ(n)`
Tower of Hanoi	`T(n) = 2T(n−1) + Θ(1)`	Not D&C; `Θ(2^n)`

14. Open Questions

How often do real interview recurrences fall into a master-theorem gap case? (Anecdotally: rare. Most are clean Case 1, 2, or 3 — but recognising the gap is itself a signal of mastery.)
Is there a “fourth case” extension covering certain f(n) = n^(c*) · log^(−k) n recurrences? (Akra–Bazzi handles them, but the master theorem proper does not.)
Does the regularity condition ever fail for natural algorithmic f(n)? (Almost never in practice; it can be constructed but isn’t a real-world worry.)

15. See Also

Recurrence Relations — what we are solving; the algebraic setting
Big-O Notation, Big-Omega and Big-Theta — the asymptotic vocabulary the theorem uses
Merge Sort — canonical Case 2 example
Quicksort — average-case Case 2; worst-case is a non-master subtractive T(n) = T(n−1) + Θ(n)
Binary Search — Case 2 with k = 0
Median of Medians — Akra–Bazzi territory (unequal split)
Divide and Conquer Paradigm — the meta-technique
Recursion vs Iteration — when D&C beats iteration and vice versa
SWE Interview Preparation MOC

vault

Explorer

Master Theorem

Master Theorem

1. Intuition — Where the Three Cases Come From

2. The Watershed Function `n^(log_b a)` — Why That Specific Exponent?

3. Tiny Worked Example — Merge Sort

4. The Three Cases — Formal Statement

Case 1 — Leaves dominate

Case 2 — Watershed match

Case 3 — Root dominates

5. Worked Examples — One Per Case (and Variations)

5.1 Case 1 — Binary Search

5.2 Case 2 — Merge Sort and Friends

5.3 Case 3 — Strassen vs. Schoolbook Matrix Multiplication

5.4 Case 1 — Karatsuba Multiplication

5.5 Why Floyd–Warshall Is Not a Master-Theorem Recurrence

5.6 Many Subproblems with Tiny Combine — Searches in Trees

6. Side-by-Side Recipe

7. Pseudocode — A Master-Theorem “Solver”

8. Gap Cases — When the Master Theorem Doesn’t Apply

9. Akra–Bazzi — The General Hammer for Unbalanced Splits

10. Common Recurrences — A Reference Table

11. Pitfalls

12. Diagram — The Recursion Tree and the Watershed

13. Common Interview Problems

14. Open Questions

15. See Also

Graph View

Table of Contents

Backlinks

vault

Explorer

Master Theorem

Master Theorem

1. Intuition — Where the Three Cases Come From

2. The Watershed Function n^(log_b a) — Why That Specific Exponent?

3. Tiny Worked Example — Merge Sort

4. The Three Cases — Formal Statement

Case 1 — Leaves dominate

Case 2 — Watershed match

Case 3 — Root dominates

5. Worked Examples — One Per Case (and Variations)

5.1 Case 1 — Binary Search

5.2 Case 2 — Merge Sort and Friends

5.3 Case 3 — Strassen vs. Schoolbook Matrix Multiplication

5.4 Case 1 — Karatsuba Multiplication

5.5 Why Floyd–Warshall Is Not a Master-Theorem Recurrence

5.6 Many Subproblems with Tiny Combine — Searches in Trees

6. Side-by-Side Recipe

7. Pseudocode — A Master-Theorem “Solver”

8. Gap Cases — When the Master Theorem Doesn’t Apply

9. Akra–Bazzi — The General Hammer for Unbalanced Splits

10. Common Recurrences — A Reference Table

11. Pitfalls

12. Diagram — The Recursion Tree and the Watershed

13. Common Interview Problems

14. Open Questions

15. See Also

Graph View

Table of Contents

Backlinks

2. The Watershed Function `n^(log_b a)` — Why That Specific Exponent?