Substitution Method

Tags: #◇CCDSALG #◇Algorithms #◇Computer Science #◇Computational Complexity #◇Efficiency #◇Algorithm Design Paradigms #◇Recursion #◇Recursion and Iteration #◇Analysis of Algorithms #◇Data Structures #◇Time Complexity #◇Space Complexity

---

◇Overview

The Substitution Method solves recurrences by guessing the form of the solution and then proving it correct using mathematical induction.

◇Key Concepts

Two-step process: guess then prove Requires mathematical induction The guess can come from the ◇Recursion Tree Method or intuition Must find appropriate constants $c$ and $n_0$

◇Details / Theory

Steps

1. Guess the form of the solution (e.g., $T(n) = O(n \log n)$).
2. Prove the guess is correct using mathematical induction:
   Base case: Verify $T(n_0) \leq c \cdot g(n_0)$ for some small $n_0$.
   Inductive step: Assume $T(k) \leq c \cdot g(k)$ for all $k < n$, then show $T(n) \leq c \cdot g(n)$.

Worked Example: $T(n) = 2T(n/2) + n$

Guess: $T(n) = O(n \log n)$, i.e., $T(n) \leq cn \log n$ for some $c > 0$.

Inductive Hypothesis: Assume $T(k) \leq ck \log k$ for all $k < n$.

Inductive Step:
$T(n) = 2T(n/2) + n$
$\leq 2 \cdot c(n/2)\log(n/2) + n$
$= cn(\log n - \log 2) + n$
$= cn \log n - cn + n$
$\leq cn \log n \quad \text{(when } c \geq 1\text{)}$

Thus $T(n) = O(n \log n)$. $\square$

Worked Example: $T(n) = T(n/2) + 1$

Guess: $T(n) = O(\log n)$, i.e., $T(n) \leq c \log n$.

Inductive Step:
$T(n) = T(n/2) + 1 \leq c \log(n/2) + 1 = c\log n - c + 1 \leq c\log n \quad \text{(when } c \geq 1\text{)}$

Tips for Guessing

Use the ◇Recursion Tree Method to get intuition for the bound. Try common forms: $O(n)$, $O(n \log n)$, $O(n^2)$, $O(\log n)$. If the proof fails, try a tighter or looser bound. Sometimes subtracting a lower-order term in the hypothesis helps (e.g., $T(n) \leq cn \log n - dn$).

◇Common Pitfalls

Making the inductive hypothesis too weak or too strong. Forgetting to verify the base case. Using $O$-notation in the inductive proof instead of concrete constants (must use actual $c$).

◇Summary

TL;DR — The Substitution Method guesses a closed-form solution to a recurrence and proves it via mathematical induction. The guess can come from intuition or the Recursion Tree Method.

◇Links

Related: ◇Master Theorem — ◇Recursion Tree Method — ◇Divide and Conquer — ◇Asymptotic Notation — ◇Correctness Source / Reference: Handout 03

◇References & Navigation

• Previous Topic: ◇Space Complexity
• Next Topic: ◇Time Complexity
• Related Notes: ◇Algorithm Analysis, ◇Core Concepts