The Substitution Method for Solving Recurrences

Introduction

Many algorithms, especially Divide and Conquer algorithms, produce recurrence relations.

To determine the running time of these algorithms, we must solve the recurrence.

The Substitution Method is the most general of these methods because it can be applied to a wide variety of recurrences. However, unlike the Master Method, it requires us to first guess the form of the solution.

---

Why is it Called the Substitution Method?

The name comes from the key step in the proof.

Suppose the recurrence is

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

Assume that

$$T(n)\le cn\log n$$

for smaller values of $n$.

Then we substitute this assumed bound into the recurrence:

$$T(n) \le 2\left(c\frac n2\log\frac n2\right)+n$$

Since we substitute the guessed solution into the recurrence, the technique is called the Substitution Method.

---

3. Steps in the Substitution Method

The substitution method consists of two steps:

Step 1

Guess the form of the solution using symbolic constants.

---

Step 2

Use mathematical induction to prove that the guess is correct and determine suitable values of the constants.

---

4. General Procedure

Suppose we have the recurrence

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

The procedure is

Step 1

Guess

$$T(n)=O(n\log n)$$

---

Step 2

Assume

$$T(k)\le ck\log k$$

for all

$$k<n$$

This is the induction hypothesis.

---

Step 3

Substitute the induction hypothesis into the recurrence.

---

Step 4

Simplify the expression.

---

Step 5

Choose suitable constants so that the inequality holds.

---

Step 6

Verify the base case.

---

5. Example 

Consider the recurrence

$$\boxed{ T(n)=2T(\lfloor n/2\rfloor)+\Theta(n) }$$

This is essentially the Merge Sort recurrence, except that it explicitly uses the floor function to ensure the recurrence is defined for integer values of n.

---

Step 1: Guess the Solution

Since the recurrence resembles Merge Sort,

we guess

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

---

Step 2: State the Induction Hypothesis

Instead of writing

$$T(n)=O(n\log n)$$

we assume

$$\boxed{ T(n)\le cn\log n }$$

for some constant

$$c>0$$

Notice that it does not use asymptotic notation inside the induction hypothesis. Instead, it uses an explicit constant c.

---

Step 3: Substitute

Using the induction hypothesis,

$$T(\lfloor n/2\rfloor) \le c\lfloor n/2\rfloor \log(\lfloor n/2\rfloor)$$

Substitute into the recurrence:

$$T(n) \le 2c\left(\frac n2\right) \log\left(\frac n2\right) +\Theta(n)$$

---

Step 4: Simplify

Since

$$\log\left(\frac n2\right) = \log n-\log2$$

and

$$\log2=1$$

we get

$$T(n) \le cn(\log n-1)+\Theta(n)$$

or

$$T(n) = cn\log n-cn+\Theta(n)$$

---

Step 5: Choose the Constant

The negative term

$$-cn$$

must dominate the hidden constant inside

$$\Theta(n)$$

Choose

$$c$$

large enough.

Then

$$T(n) \le cn\log n$$

Thus,

the induction step is complete.

---

Step 6: Base Case

Note that the base case must also satisfy the induction hypothesis.

Choose

$$n_0=2$$

and select

$$c$$

large enough so that

$$T(2)\le2c\log2$$

and

$$T(3)\le3c\log3$$

Hence,

the induction starts correctly.

---

Final Result

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