Skip to main content

Recurrences: Substitution, Recursion Tree, Master Theorem

What This Concept Is​

A recurrence expresses the cost of a recursive algorithm in terms of the cost on smaller inputs:

$$T(n) = a \cdot T(n/b) + f(n),$$

meaning the algorithm makes $a$ recursive calls on inputs of size $n/b$ and does $f(n)$ non-recursive work (split plus combine). The base case is stated separately (typically $T(1) = \Theta(1)$).

Three techniques solve almost every recurrence you meet at this stage:

  1. Substitution (CLRS §4.3). Guess a bound, prove it by strong induction. Most rigorous; good when the master theorem does not apply or when you need the inequality explicitly (e.g., to plug into a subsequent proof).
  2. Recursion tree (CLRS §4.4). Draw the call tree, compute work per level, sum across levels. Best for intuition and for recurrences that split unevenly or have mixed terms.
  3. Master theorem (CLRS §4.5). A closed-form shortcut for $T(n) = a T(n/b) + f(n)$: compare $f(n)$ to the "critical exponent" $n^{\log_b a}$. Three cases, one answer each.

A fourth tool, the Akra-Bazzi method (CLRS §4.7), generalizes the master theorem to unequal split sizes such as $T(n) = T(n/3) + T(2n/3) + n$. Learn it once; you will need it for QuickSelect-style analyses.

Why It Matters Here​

Recurrences convert recursive code into asymptotics. Without them, divide-and-conquer and DP analyses collapse into guesses. Mergesort, binary search, quicksort (average case), Strassen, the closest-pair algorithm, the Karatsuba and FFT multiplications, and most D&C routines are recurrences with known solutions. A recurrence is to a recursive algorithm what a summation is to a loop (concept 2).

They also tell you whether a proposed algorithm can meet a target complexity before you implement it. A recurrence $T(n) = 3T(n/2) + n$ gives $\Theta(n^{\log_2 3}) \approx \Theta(n^{1.585})$ - if your target was $O(n \log n)$, stop coding and redesign the combine step.

Concrete Example​

Example 1 (mergesort). $T(n) = 2 T(n/2) + n$, $T(1) = 1$.

Recursion tree view.

  • Level 0: 1 node of size $n$, does $n$ work.
  • Level 1: 2 nodes of size $n/2$, each doing $n/2$ work, total $n$.
  • Level $k$: $2^k$ nodes of size $n/2^k$, total work $n$.
  • Depth: $\log_2 n + 1$ levels, each contributing $n$ work.

Total: $n \cdot (\log_2 n + 1) = \Theta(n \log n)$.

Master theorem view. $a = 2$, $b = 2$, $f(n) = n$. The critical exponent is $n^{\log_b a} = n^1 = n$. Case 2 applies ($f(n) = \Theta(n^{\log_b a})$), yielding $T(n) = \Theta(n \log n)$. Same answer.

Substitution check. Guess $T(n) \le c , n \log n$. Then $$T(n) \le 2 \cdot c (n/2) \log(n/2) + n = c n \log n - c n + n \le c n \log n$$ for any $c \ge 1$. Base case $T(1) \le c \cdot 1 \cdot \log 1 = 0$ fails at $n = 1$, so start the induction at $n = 2$ and absorb the base into the constant. Lesson: substitution often needs a stronger inductive hypothesis (subtract a lower-order term like $-dn$) to carry the step through.

Example 2 (binary search). $T(n) = T(n/2) + \Theta(1)$. Master theorem: $a = 1$, $b = 2$, $f(n) = 1$. Critical exponent $n^{\log_2 1} = n^0 = 1 = f(n)$. Case 2 gives $T(n) = \Theta(\log n)$.

Example 3 (Strassen). $T(n) = 7 T(n/2) + \Theta(n^2)$. Critical exponent $n^{\log_2 7} \approx n^{2.807} > n^2$. Case 1 gives $T(n) = \Theta(n^{\log_2 7})$ - the first sub-cubic matrix multiplication.

Example 4 (linear recurrence). $T(n) = T(n-1) + n$, $T(0) = 0$. Unwind: $$T(n) = \sum_{i=1}^{n} i = \frac{n(n+1)}{2} = \Theta(n^2).$$ Master theorem does not apply (not $a T(n/b)$ form). The recursion-tree/sum view does.

Common Confusion / Misconceptions​

  • "The master theorem solves every recurrence." It solves only $T(n) = a T(n/b) + f(n)$ with $a \ge 1$, $b > 1$, $f$ asymptotically positive, and $f$ in one of the three cases. Recurrences like $T(n) = T(n-1) + n$, $T(n) = T(\sqrt{n}) + 1$, or $T(n) = T(n/3) + T(2n/3) + n$ require substitution, recursion tree, or Akra-Bazzi.
  • "Case 3 is automatic when $f$ grows faster." Case 3 additionally requires the regularity condition $a \cdot f(n/b) \le k \cdot f(n)$ for some constant $k < 1$ and all sufficiently large $n$. Most polynomial $f$ satisfy it, but $f(n) = n^2 / \log n$ is a canonical case where it fails and a direct analysis is needed.
  • "The guess in substitution has to be exact." It has to be correct - too large a guess still verifies, just uselessly. The art is guessing something tight enough that the induction carries through; if it does not, you either under-subtracted a lower-order term or guessed too loosely.
  • "Unequal splits mean master theorem just with a different $b$." No - $T(n) = T(n/3) + T(2n/3) + n$ is genuinely different from $T(n) = 2 T(n/2) + n$. Use Akra-Bazzi; the answer is still $\Theta(n \log n)$, but the path to it matters.
  • "Floors and ceilings change the answer." They almost never do for polynomial $f$; the master theorem, as stated in CLRS §4.6, is robust to $\lfloor n/b \rfloor$ vs $\lceil n/b \rceil$. Do not drop a proof down to this level unless something is genuinely fishy about your split.
  • "The combine cost is always polynomial." It can be $f(n) = n \log n$, $f(n) = n / \log n$, or worse. Polynomial $f$ is where master theorem is cleanest; non-polynomial $f$ often needs recursion tree or Akra-Bazzi.

How To Use It​

Triage protocol:

  1. If the recurrence is $T(n) = a T(n/b) + f(n)$ with $a, b$ constant and $f$ polynomial, try the master theorem first.
  2. If the recurrence has uneven splits or polylog factors the master theorem handles awkwardly, use Akra-Bazzi or a recursion tree.
  3. If the recurrence is subtractive ($T(n) = T(n-c) + f(n)$) or mixed, unroll the first few levels and spot the pattern, then prove by substitution.
  4. Always verify the base case - an inductive proof that ignores $n = 1$ (or where $f$ is negative) is unsound.
  5. Strengthen the inductive hypothesis with a lower-order term (e.g., guess $c n \log n - d n$ instead of $c n \log n$) when the direct guess does not go through.
  6. Sanity-check with a numerical simulation: compute $T(n)$ for $n = 1, 2, 4, 8, 16, \ldots$ from the recurrence and verify the ratio $T(2n)/T(n)$ matches your claimed growth.

When a recurrence resists all three methods, the usual culprits are (a) the recursive argument is non-monotone, (b) the combine cost depends on state across calls (not just input size), or (c) the split is randomized and you need expectation over the split point. In case (c), Akra-Bazzi applied to the expected recurrence typically works.

Keep this small table handy.

RecurrenceSolution
$T(n) = T(n/2) + 1$$\Theta(\log n)$
$T(n) = 2 T(n/2) + n$$\Theta(n \log n)$
$T(n) = 2 T(n/2) + 1$$\Theta(n)$
$T(n) = T(n-1) + 1$$\Theta(n)$
$T(n) = T(n-1) + n$$\Theta(n^2)$
$T(n) = 2 T(n-1) + 1$$\Theta(2^n)$
$T(n) = 7 T(n/2) + n^2$$\Theta(n^{\log_2 7})$
$T(n) = T(n/3) + T(2n/3) + n$$\Theta(n \log n)$ (Akra-Bazzi)
$T(n) = T(\sqrt n) + 1$$\Theta(\log \log n)$ (substitute $m = \log n$)
$T(n) = T(n/2) + \log n$$\Theta(\log^2 n)$ (recursion tree)
$T(n) = 2 T(n/4) + \sqrt n$$\Theta(\sqrt n \log n)$ (master, case 2)

Transfer / Where This Shows Up Later​

  • S1 M5 (problem solving) framed "estimate before you optimize." Recurrences are the formal estimate for recursive algorithms.
  • S4 (systems) uses recurrences for cache-oblivious algorithms: $T(n) = 2 T(n/2) + n/B$ for I/O-efficient merging, where $B$ is the cache line size.
  • S5 (OS) analyzes parallel work-stealing schedulers by recurrences on task-tree depth.
  • S6 (databases) models B-tree operations as $T(n) = T(n/B) + 1 = \Theta(\log_B n)$; LSM compaction amortization rides on a similar recurrence (concept 4).
  • S7 (architecture) writes fitness functions for latency that assume a particular recurrence for sharded requests (fan-out trees are $\Theta(\log n)$-deep).
  • S8 (distributed systems) solves tree broadcast and aggregation as recurrences with $a$ fan-out children per level.

The recursion tree view of this page is also the exact mental model used for DP state-space sizing in cluster 4.

Later-semester anchors: S2 M2 sorts (mergesort $2T(n/2)+n$; quicksort expected $2T(n/2)+n$; selection $T(n) \le T(n/5) + T(7n/10) + n$ for median-of-medians) all reduce to a single named recurrence. S2 M3 analyzes shortest-path and flow via fixed-point recurrences (Bellman-Ford, Edmonds-Karp). S2 M4 states DP runtime is a recurrence $T(n) = \text{(states)} \cdot \text{(transition)}$ in disguise.

Check Yourself​

  1. State the three cases of the master theorem and the decision rule that picks each.
  2. Why does $T(n) = T(n-1) + 1$ solve to $\Theta(n)$, not $\Theta(\log n)$?
  3. When would you prefer a recursion tree over the master theorem?
  4. Give an example where the regularity condition of Case 3 fails.
  5. Translate "QuickSelect's expected runtime" into a recurrence and show how Akra-Bazzi produces $\Theta(n)$.
  6. For $T(n) = 2 T(n/2) + n / \log n$, show master theorem does not cleanly apply (Case 3 regularity fails) and give the correct answer via recursion tree.
  7. Why does the base-case cost $\Theta(1)$ rarely affect the asymptotic answer? Give one recurrence where it would dominate.

Mini Drill or Application​

Solve each recurrence. Give $\Theta$ where possible.

  1. $T(n) = 4 T(n/2) + n$
  2. $T(n) = 3 T(n/2) + n^2$
  3. $T(n) = 2 T(n/2) + n \log n$
  4. $T(n) = T(n/2) + T(n/3) + n$
  5. $T(n) = T(n-1) + \log n$
  6. $T(n) = 2 T(n-1) + n$
  7. Implementation drill. Write a function solve_recurrence(a, b, f) that returns the master-theorem class (case-1, case-2, case-3, or does-not-apply) given a, b, and a callable f(n). Test on the table above. Complexity: $\Theta(1)$ per query (after sampling $f$ at two sizes to estimate its polynomial degree).

Read This Only If Stuck​