The Substitution Method is a fundamental technique for solving recurrence relations, particularly those encountered in the analysis of algorithms. It's a powerful tool for understanding the time complexity of recursive algorithms, a key skill for competitive exams like GATE Computer Science.

A recurrence relation is an equation that defines a sequence recursively; that is, each term of the sequence is defined as a function of the preceding terms. In algorithm analysis, recurrence relations often describe the running time of a recursive algorithm.

The Substitution Method involves two main steps:

1. Guess the form of the solution: Based on the recurrence relation and base cases, hypothesize a general form for the solution (e.g., $T(n) = O(n^2)$).
2. Prove the guess using mathematical induction: Show that the hypothesized solution holds true for all values of n by using induction.

To guess the form, we often expand the recurrence relation a few times to observe a pattern. For example, if $T(n) = 2T(n/2) + n$, expanding it might reveal terms like $n$, $2(n/2)$, $4(n/4)$, etc., suggesting a linear or $n \log n$ complexity.

Once a guess is made, say $T(n) \le c \cdot f(n)$ for some constant $c$ and function $f(n)$, we prove it by induction:

• Base Case: Show the inequality holds for a small value of $n$ (e.g., $n=1$ or $n=n_0$).
• Inductive Hypothesis: Assume the inequality holds for all $k < n$.
• Inductive Step: Prove the inequality holds for $n$ using the inductive hypothesis.

The main challenge is making the correct initial guess. Sometimes, the guessed form might be too loose, and the inductive step fails. In such cases, you might need to refine the guess, perhaps by adding a lower-order term (e.g., guessing $T(n) = c_1 n \log n + c_2 n$ instead of just $c \cdot n \log n$). Always ensure your constants are positive and that the base cases are handled correctly.

Let's solve $T(n) = T(n-1) + c$ with $T(1) = k$.

Guess: Expanding, we get $T(n) = T(n-1) + c = T(n-2) + 2c = \dots = T(1) + (n-1)c = k + (n-1)c$. This looks linear, $O(n)$. Let's guess $T(n) \le C n$ for some constant $C$.

Proof by Induction:

• Base Case: $T(1) = k$. We need $k \le C \cdot 1$. Choose $C \ge k$.
• Inductive Hypothesis: Assume $T(m) \le C m$ for all $m < n$.
• Inductive Step: $T(n) = T(n-1) + c$. By IH, $T(n-1) \le C(n-1)$. So, $T(n) \le C(n-1) + c = Cn - C + c$. We want $Cn - C + c \le Cn$. This requires $-C + c \le 0$, or $C \ge c$. Thus, if we choose $C = \max(k, c)$, the guess $T(n) = O(n)$ is proven.

While the substitution method is versatile, it can be cumbersome. The Master Theorem provides a more direct way to solve recurrences of the form $T(n) = aT(n/b) + f(n)$, and the Recursion Tree method offers a visual approach to understand the expansion process.