Mastering Recurrence Relations: The Substitution Method

Verified Sources

May 26, 2026

In computer science, analyzing the execution time of recursive algorithms requires solving a recurrence relation (https://mitpress.mit.edu/9780262046305/introduction-to-algorithms/). A classic example is the recurrence:

$T(n) = 2T(n/2) + n$

This equation frequently arises in divide-and-conquer algorithms, such as Mergesort, where a problem of size $n$ is split into two equal subproblems of size $n/2$ , alongside a linear cost $n$ for splitting and recombining the subproblems (https://mitpress.mit.edu/9780262046305/introduction-to-algorithms/).

To establish an asymptotic upper bound for $T(n)$ , we can use the substitution method (https://mitpress.mit.edu/9780262046305/introduction-to-algorithms/). This method leverages mathematical induction to prove that a guessed bound holds true for all inputs larger than a baseline value $n_0$ (https://web.stanford.edu/class/archive/cs/cs161/cs161.1168/).

Visualizing the Recurrence Tree

To formulate a strong initial guess, we can visualize how the recurrence splits. The total work is the sum of the work done at each level of the recursion tree:

Summing the costs across any level $i$ yields a constant cost of $n$ per level. Since the tree has a depth of $\log_2 n$ levels, the total complexity is visually estimated to be $O(n \log n)$ (https://web.stanford.edu/class/archive/cs/cs161/cs161.1168/).

Introduction to Algorithms (CLRS) - Chapter 4: Divide-and-Conquer and Recurrences. ↩ ↩² ↩³
Mathematical Induction for Recurrences - Stanford CS161 Lecture Notes on solving recurrences using the substitution method. ↩ ↩²

Formulating a Good Guess

Before starting the substitution method, always sketch a quick recursion tree. If the tree reveals that every level does $n$ work and there are $\log_2 n$ levels, your guess should be $O(n \log n)$ . This ensures you do not waste algebraic effort proving a bound that is too tight or too loose.

Mathematical Induction Walkthrough

1
Step 1
Based on our visual analysis, we guess that $T(n) \le c n \log_2 n$ for some constant $c > 0$ and all $n \ge n_0$ . This formulation represents our inductive hypothesis.
2
Step 2
We assume the inductive hypothesis holds true for all positive numbers smaller than $n$ , which specifically includes $n/2$ . Thus, we substitute the hypothesis into the recurrence relation: $T(n/2) \le c (n/2) \log_2(n/2)$ . Inserting this into the original equation yields: $T(n) \le 2\left(c \frac{n}{2} \log_2\left(\frac{n}{2}\right)\right) + n$ .
3
Step 3
Simplify the substituted inequality using the laws of logarithms. We know that $\log_2(n/2) = \log_2 n - \log_2 2 = \log_2 n - 1$ . Expanding the expression gives: $T(n) \le c n (\log_2 n - 1) + n = c n \log_2 n - c n + n$ .
4
Step 4
To complete the induction, we must show that our simplified inequality is less than or equal to our target bound: $c n \log_2 n - c n + n \le c n \log_2 n$ . This inequality holds true if and only if $-c n + n \le 0$ , which simplifies directly to $c \ge 1$ .
5
Step 5
Show that the boundary condition holds. If we assume a base case $T(1) = 1$ , our inductive hypothesis yields $T(1) \le c \cdot 1 \log_2 1 = 0$ , which contradicts the base case. Because asymptotic bounds only require the inequality to hold for $n \ge n_0$ , we can choose $n_0 = 2$ and $n_0 = 3$ as our base cases. With $T(2) = 2T(1) + 2 = 4$ , we choose $c$ large enough (e.g., $c \ge 2$ ) to satisfy the base cases.

The Base Case Trap

A common pitfall in mathematical induction is neglecting the base case. If your base case is $n = 1$ , $T(1) \le c \cdot 1 \log_2 1$ evaluates to $T(1) \le 0$ , which is impossible for positive running times. Always remember that asymptotic notation only requires the bound to hold for $n \ge n_0$ . You can freely choose $n_0 = 2$ or $n_0 = 3$ as your base cases for induction [(https://web.stanford.edu/class/archive/cs/cs161/cs161.1168/)].

Mathematical Induction for Recurrences - Stanford CS161 Lecture Notes on solving recurrences using the substitution method. ↩

A rigorous mathematical technique where we guess the form of the solution and prove it using mathematical induction. Highly precise but requires a good initial guess.

$\text{Key Advantage: Perfect mathematical rigor.}$ $\text{Key Disadvantage: Hard to formulate a guess for complex equations.}$

Advanced Substitution Strategies & Edge Cases

Knowledge Check

Question 1 of 3

Q1Single choice

Which of the following is the correct inductive hypothesis to prove that $T(n) = 2T(n/2) + n$ is $O(n \log n)$ ?

$T(n) \ge c n \log_2 n$ for all $n \ge n_0$

$T(n) \le c n \log_2 n$ for all $n \ge n_0$ and some constant $c > 0$

$T(n) = c n^2$ for all $n$

$T(n) < n \log_2 n$ for all $n$

Explore Related Topics

Dynamic Programming and Greedy Algorithms: Comparative Analysis, Failure Cases, and Core DP Properties

The article contrasts greedy algorithms with dynamic programming, shows when greedy fails and DP is necessary, and explains DP’s core properties of optimal substructure and overlapping subproblems.

Greedy makes irrevocable local choices and works only with the $greedy\text{-}choice$ property, while DP stores and reuses subproblem results to guarantee optimality.
Counterexamples such as coin change ( $\{1,3,4\}$ for amount 6) and $0/1$ knapsack illustrate failures of greedy and the need for DP recurrences like $dp[x]=1+\min_{c\le x}dp[x-c]$ and $dp[i][w]=\max(dp[i-1][w],\,v_i+dp[i-1][w-w_i])$ .
DP relies on $optimal\ substructure$ to form recurrences and on overlapping subproblems to justify caching.
Design steps: recognize structure, detect repetition, formulate recurrence, compute once (memoization/tabulation), optionally reconstruct solution.
Rule of thumb: use greedy if local choices can be proved globally safe; otherwise apply DP.

Syntax-Directed Translation: Infix to Prefix Notation

The module shows how a syntax‑directed translation scheme using only synthesized attributes can convert infix arithmetic expressions into prefix (Polish) notation while preserving operator precedence and left‑associativity.

Grammar: E → E + T | E - T | T; T → T * F | F; F → digit, enforcing precedence ( *  > + / - ).
Semantic actions compute a val string for each non‑terminal, concatenating the operator before its operand strings.
Example results: 9 - 5 + 2 → + - 9 5 2; 9 - 5 * 2 → - 9 * 5 2.
Synthesized (S‑attributed) attributes allow immediate bottom‑up evaluation during LR‑style parsing.
Left‑recursive rules enable left‑associativity; to use LL parsers the grammar must be transformed and inherited attributes introduced.

Asymptotic Notation in Algorithm Analysis

Browse all research articles