Recurrence Relation and Solving using Substitution Method

A recurrence relation is a mathematical equation that defines a function in terms of its value on smaller inputs, typically used to express the running time of recursive algorithms.

---

What is a Recurrence Relation?

A recurrence relation describes the time complexity of a recursive algorithm by relating $T(n)$ to $T$ of smaller values. It consists of:

• Recursive case — expresses $T(n)$ in terms of smaller subproblems (e.g., $T(n/2)$, $T(n-1)$)
• Base case — gives the value for the smallest input (e.g., $T(1) = 1$)

Example: $T(n) = 2T(n/2) + n$ represents the recurrence for Merge Sort.

---

Methods to Solve Recurrence Relations

There are three main methods to solve recurrence relations:

• Substitution Method — Guess the solution, then prove it correct using mathematical induction.
• Recursion Tree Method — Expand the recurrence into a tree, sum up the costs at each level.
• Master Method — Directly apply the Master Theorem formula for recurrences of the form $T(n) = aT(n/b) + f(n)$.

---

Proof: $T(n) = 2T(n/2) + 1$ is $O(n)$ using Substitution Method

Given: $T(n) = 2T(n/2) + 1$

Step A: Guess the solution

We guess that $T(n) = O(n)$, i.e., $T(n) \leq cn$ for some constant $c > 0$.

Step B: Assume it holds for smaller inputs (Inductive Hypothesis)

Assume $T(n/2) \leq c(n/2)$ for all values less than $n$.

Step C: Substitute into the recurrence

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

Substituting the hypothesis:

$$T(n) \leq 2 \cdot c(n/2) + 1$$

$$T(n) \leq cn + 1$$

Step D: We need to show $T(n) \leq cn$

From above, $T(n) \leq cn + 1$

This does not directly satisfy $T(n) \leq cn$. So we strengthen our guess.

Step E: Strengthen the guess

Let us guess $T(n) \leq cn - d$ for constants $c > 0$ and $d > 0$.

Assume $T(n/2) \leq c(n/2) - d$

Substituting:

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

$$T(n) \leq 2[c(n/2) - d] + 1$$

$$T(n) \leq cn - 2d + 1$$

$$T(n) \leq cn - d \quad \text{(if } -2d + 1 \leq -d \text{, i.e., } d \geq 1\text{)}$$

Step F: Verify the condition

Choose $d = 1$, then:

$$T(n) \leq cn - 2(1) + 1 = cn - 1 \leq cn - d$$

This satisfies our guess $T(n) \leq cn - d$.

Step G: Verify the base case

For $T(1) = 1$ (base case), we need:

$$T(1) \leq c(1) - d$$

$$1 \leq c - 1$$

$$c \geq 2$$

Choose $c = 2$ and $d = 1$, both conditions are satisfied.

---

Conclusion

Since we have proven by induction that $T(n) \leq cn - d \leq cn$ for $c = 2$ and $d = 1$, we conclude:

$$\boxed{T(n) = O(n)}$$

The substitution method works by guessing the form of the solution and then proving it correct using mathematical induction. The key trick is to strengthen the hypothesis when the direct guess fails.