Substitution Method - Example Problems

 

Problem-1

Use the substitution method to show that

$$T(n)=T(n-1)+n$$

has the asymptotic upper bound

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

---

Step 1: Guess the Solution

Looking at the recurrence,

$$T(n)=T(n-1)+n,$$

the additional work performed at each recursive call is $n$.

Since

$$1+2+3+\cdots+n=\frac{n(n+1)}{2},$$

it is reasonable to guess that

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

---

Step 2: State the Induction Hypothesis

Assume that for all values smaller than $n$,

$$\boxed{T(k)\le ck^2}$$

for some constant

$$c>0.$$

In particular,

$$T(n-1)\le c(n-1)^2.$$

---

Step 3: Substitute into the Recurrence

Using the recurrence,

$$T(n)=T(n-1)+n$$

Substitute the induction hypothesis:

$$T(n) \le c(n-1)^2+n.$$

---

Step 4: Expand the Square

Recall that

$$(n-1)^2=n^2-2n+1.$$

Therefore,

$$T(n) \le c(n^2-2n+1)+n.$$

Expanding,

$$T(n) \le cn^2-2cn+c+n.$$

---

Step 5: Rearrange

$$T(n) \le cn^2-(2c-1)n+c.$$

To prove

$$T(n)\le cn^2,$$

we require

$$-(2c-1)n+c\le0.$$

---

Step 6: Choose Suitable Constants

If

$$c\ge1,$$

then

$$2c-1\ge1.$$

Hence

$$-(2c-1)n+c$$

is negative for sufficiently large values of $n$.

For example, choosing

$$\boxed{c=1},$$

gives

$$-n+1\le0$$

for all

$$n\ge1.$$

Thus,

$$T(n)\le cn^2.$$

---

Step 7: Verify the Base Case

Assume

$$T(1)=1.$$

Then

$$T(1)=1\le c(1)^2.$$

Choosing

$$c\ge1$$

satisfies the base case.

---

Conclusion

Since both the induction step and the base case hold,

$$\boxed{T(n)\le cn^2}$$

for some constant $c$.

Therefore,

$$\boxed{T(n)=O(n^2).}$$

---

Complete Induction Proof (Exam Style)

Given:

$$T(n)=T(n-1)+n$$

Guess:

$$T(n)=O(n^2)$$

Assume that

$$T(n-1)\le c(n-1)^2$$

for some constant $c>0$.

Then,

$$\begin{aligned} T(n) &=T(n-1)+n\\ &\le c(n-1)^2+n\\ &=c(n^2-2n+1)+n\\ &=cn^2-2cn+c+n\\ &=cn^2-(2c-1)n+c\\ &\le cn^2 \end{aligned}$$

provided $c\ge1$ and $n$ is sufficiently large.

For the base case,

$$T(1)\le c,$$

which is true for $c\ge1$.

Hence,

$$\boxed{T(n)=O(n^2).}$$

---

Note for Students

The bound $O(n^2)$is correct but not tight. If we expand the recurrence,

$$T(n)=T(1)+2+3+\cdots+n =\Theta(n^2),$$

so the tight asymptotic bound is

$$\boxed{T(n)=\Theta(n^2).}$$

Problem-3

Use the substitution method to show that

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

has the asymptotic upper bound

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

Assume

$$T(1)=\Theta(1).$$

---

Step 1: Guess the Solution

Since this is the recurrence for Merge Sort, we guess

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

---

Step 2: State the Induction Hypothesis

Assume that for all smaller values,

$$\boxed{T(k)\le ck\log k}$$

for some constant

$$c>0.$$

In particular,

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

---

Step 3: Substitute into the Recurrence

The recurrence is

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

Substitute the induction hypothesis.

$$\begin{aligned} T(n) &\le 2\left(c\frac n2\log\frac n2\right)+n. \end{aligned}$$

---

Step 4: Simplify

Since

$$2\times\frac n2=n,$$

we get

$$T(n) \le cn\log\frac n2+n.$$

Using the logarithm identity

$$\log\frac n2=\log n-\log2,$$

and

$$\log2=1,$$

we obtain

$$\begin{aligned} T(n) &\le cn(\log n-1)+n\\ &=cn\log n-cn+n\\ &=cn\log n-(c-1)n. \end{aligned}$$

---

Step 5: Choose Suitable Constants

To prove

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

we require

$$-(c-1)n\le0.$$

This holds whenever

$$\boxed{c\ge1.}$$

Hence,

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

Thus, the induction step is complete.

---

Step 6: Verify the Base Case

Choose

$$n_0=2.$$

For

$$n=2,$$
$$T(2)\le2c\log2=2c.$$

Choose

$$c$$

large enough so that

$$T(2)\le2c.$$

Hence, the base case is satisfied.

---

Conclusion

Since both the induction step and the base case hold,

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

for sufficiently large $n$.

Therefore,

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

---

Complete Exam-Style Proof

Given

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

Guess

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

Assume

$$T(n/2)\le c\frac n2\log\frac n2.$$

Then

$$\begin{aligned} T(n) &=2T(n/2)+n\\ &\le2\left(c\frac n2\log\frac n2\right)+n\\ &=cn\log\frac n2+n\\ &=cn(\log n-1)+n\\ &=cn\log n-cn+n\\ &=cn\log n-(c-1)n\\ &\le cn\log n, \end{aligned}$$

provided

$$c\ge1.$$

Choose $c$ large enough to satisfy the base case.

Hence,

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

---

Proving the Tight Bound $\mathrm{\Theta }(n\log n)$

To show the solution is tight, we also prove the lower bound.

Assume

$$T(n)\ge dn\log n$$

for some constant $d>0$

Using the recurrence,

$$\begin{aligned} T(n) &\ge2\left(d\frac n2\log\frac n2\right)+n\\ &=dn(\log n-1)+n\\ &=dn\log n-dn+n\\ &=dn\log n+(1-d)n. \end{aligned}$$

If

$$d\le1,$$

then

$$(1-d)n\ge0,$$

so

$$T(n)\ge dn\log n.$$

Thus,

$$\boxed{T(n)=\Omega(n\log n).}$$

Combining the upper and lower bounds,

$$\boxed{T(n)=\Theta(n\log n).}$$

​

Problem-4

Use the substitution method to show that

$$T(n)=2T\left(\frac n2+17\right)+n$$

has the asymptotic upper bound

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

---

Step 1: Guess the Solution

Since the recurrence is similar to the Merge Sort recurrence,

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

we guess

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

for some constant $c>0$

To avoid changing constants during the proof, strengthen the induction hypothesis.

Assume

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

where $d>0$.

Then

$$\begin{aligned} T(n) &\le 2\left[ c\left(\frac n2+17\right) \log\left(\frac n2+17\right) - d\left(\frac n2+17\right) \right] +n. \end{aligned}$$

Using

$$\log\left(\frac n2+17\right)\le\log n,$$

we obtain

$$T(n) \le cn\log n + 34c\log n - dn - 34d + n.$$

Rearranging,

$$T(n) \le cn\log n - (d-1)n + 34c\log n - 34d.$$

Choose $d>1$. Since $n$ grows faster than $\log n$,

$$(d-1)n > 34c\log n$$

for sufficiently large $n$.

Hence,

$$T(n) \le cn\log n-dn.$$

Therefore, the induction hypothesis is preserved.

---

Conclusion

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

​

Problem-5

Use the substitution method to show that

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

has the asymptotic upper bound

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

---

Step 1: Guess the Solution

Observe that

• Each recursive call divides the problem by 3.
• There are 2 recursive calls.
• The work outside recursion is $n$.

Since

$$n^{\log_3 2}=n^{0.63},$$

the linear term dominates. Hence, we guess

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

---

Step 2: State the Induction Hypothesis

Assume that for all smaller values,

$$\boxed{T(k)\le ck}$$

for some constant

$$c>0.$$

In particular,

$$T\left(\frac n3\right)\le c\frac n3.$$

---

Step 3: Substitute into the Recurrence

The given recurrence is

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

Using the induction hypothesis,

$$\begin{aligned} T(n) &\le 2\left(c\frac n3\right)+n\\[2mm] &= \frac{2c}{3}n+n. \end{aligned}$$

---

Step 4: Simplify

Factor out $n$:

$$T(n) \le \left(\frac{2c}{3}+1\right)n.$$

To prove

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

we need

$$\frac{2c}{3}+1\le c.$$

---

Step 5: Find the Constant

Solve the inequality:

$$\begin{aligned} \frac{2c}{3}+1 &\le c\\ 1 &\le c-\frac{2c}{3}\\ 1 &\le \frac{c}{3}\\ c &\ge 3. \end{aligned}$$

Choose

$$\boxed{c=3.}$$

Then

$$T(n)\le3n.$$

Thus, the induction step is proved.

---

Step 6: Verify the Base Case

Assume

$$T(1)=k,$$

where $k$ is a constant.

Choose

$$c\ge\max\{3,k\}.$$

Then

$$T(1)\le c,$$

so the base case is satisfied.

---

Conclusion

Since both the induction step and the base case hold,

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

for some constant $c$.

Therefore,

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

---

Complete Exam-Style Proof

Given

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

Guess

$$T(n)=O(n).$$

Assume

$$T(n/3)\le c\frac n3$$

for some constant $c>0$.

Then,

$$\begin{aligned} T(n) &=2T(n/3)+n\\ &\le2\left(c\frac n3\right)+n\\ &=\frac{2c}{3}n+n\\ &=\left(\frac{2c}{3}+1\right)n. \end{aligned}$$

To satisfy

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

we require

$$\frac{2c}{3}+1\le c,$$

which gives

$$c\ge3.$$

Choose $c=3$. The base case also holds for a sufficiently large $c$.

Hence,

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

---

Tight Bound

To prove the lower bound, assume

$$T(n)\ge dn$$

for some constant $d>0$

Then,

$$\begin{aligned} T(n) &\ge2\left(d\frac n3\right)+n\\ &=\left(\frac{2d}{3}+1\right)n. \end{aligned}$$

To show

$$T(n)\ge dn,$$

we need

$$\frac{2d}{3}+1\ge d.$$

This simplifies to

$$d\le3.$$

Choose

$$d=3.$$

Hence,

$$T(n)=\Omega(n).$$

Combining the upper and lower bounds,

$$\boxed{T(n)=\Theta(n).}$$

​

Problem-6

Use the substitution method to show that

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

has the asymptotic upper bound

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

Assume

$$T(1)=\Theta(1).$$

---

Step 1: Guess the Solution

Observe that

• Number of recursive calls = 4
• Each subproblem size = $n/2$
  
• Work outside recursion = $n$
  

Since the recurrence is similar to one solved using the Master Theorem,

$$n^{\log_24}=n^2,$$

we guess

$$\boxed{T(n)=O(n^2)}.$$

---

Step 2: State the Induction Hypothesis

Assume that for all smaller values,

$$\boxed{T(k)\le ck^2}$$

for some constant

$$c>0.$$

In particular,

$$T(n/2)\le c\left(\frac n2\right)^2.$$

---

Step 3: Substitute into the Recurrence

Given

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

substitute the induction hypothesis:

$$\begin{aligned} T(n) &\le 4\left(c\left(\frac n2\right)^2\right)+n. \end{aligned}$$

---

Step 4: Simplify

Since

$$\left(\frac n2\right)^2=\frac{n^2}{4},$$

we obtain

$$\begin{aligned} T(n) &\le 4\left(c\frac{n^2}{4}\right)+n\\ &= cn^2+n. \end{aligned}$$

---

Step 5: Problem Encountered

We want to prove

$$T(n)\le cn^2,$$

but we obtained

$$T(n)\le cn^2+n.$$

The extra $+n$ term prevents us from completing the proof.

This is exactly the type of situation discussed  under "A trick of the trade: subtracting a low-order term."

The induction hypothesis is not strong enough.

---

Step 6: Strengthen the Induction Hypothesis

Instead of assuming

$$T(n)\le cn^2,$$

assume

$$\boxed{T(n)\le cn^2-dn}$$

where

$$d>0.$$

---

Step 7: Substitute Again

Using the stronger hypothesis,

$$\begin{aligned} T(n) &\le 4\left(c\left(\frac n2\right)^2-d\frac n2\right)+n. \end{aligned}$$

---

Step 8: Simplify

Expanding,

$$\begin{aligned} T(n) &= 4\left(c\frac{n^2}{4}-d\frac n2\right)+n\\ &= cn^2-2dn+n\\ &= cn^2-(2d-1)n. \end{aligned}$$

---

Step 9: Choose Suitable Constant

We want

$$T(n)\le cn^2-dn.$$

Therefore,

$$cn^2-(2d-1)n \le cn^2-dn.$$

Subtract $cn^2$ from both sides:

$$-(2d-1)n\le-dn.$$

Multiplying by $-1$ (which reverses the inequality),

$$2d-1\ge d.$$

Hence,

$$d\ge1.$$

Choose

$$\boxed{d=1.}$$

Thus,

$$T(n)\le cn^2-n,$$

which is exactly the strengthened induction hypothesis.

---

Step 10: Base Case

Suppose

$$T(1)=k.$$

Choose

$$c$$

large enough so that

$$T(1)\le c-d.$$

Hence, the base case is satisfied.

---

Conclusion

Since the induction step and base case hold,

$$\boxed{T(n)\le cn^2-dn}$$

for suitable constants $c$ and $d$.

Therefore,

$$\boxed{T(n)=O(n^2).}$$

---

Complete Exam-Style Proof

Given

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

Guess

$$T(n)=O(n^2).$$

The initial hypothesis

$$T(n)\le cn^2$$

fails because

$$T(n)\le cn^2+n.$$

Hence, strengthen the induction hypothesis:

$$T(n)\le cn^2-dn.$$

Assume

$$T(n/2)\le c\left(\frac n2\right)^2-d\left(\frac n2\right).$$

Then,

$$\begin{aligned} T(n) &=4T(n/2)+n\\ &\le4\left(c\frac{n^2}{4}-d\frac n2\right)+n\\ &=cn^2-2dn+n\\ &=cn^2-(2d-1)n. \end{aligned}$$

To satisfy

$$T(n)\le cn^2-dn,$$

we require

$$2d-1\ge d,$$

which gives

$$d\ge1.$$

Choose $d=1$. The base case holds for a sufficiently large $c$.

Hence,

$$\boxed{T(n)=O(n^2).}$$

---

Proving the Tight Bound

To show that the solution is tight, we prove a matching lower bound.

Assume

$$T(n)\ge en^2$$

for some constant $e>0$

Then,

$$\begin{aligned} T(n) &\ge4e\left(\frac n2\right)^2+n\\ &=en^2+n\\ &\ge en^2. \end{aligned}$$

Thus,

$$\boxed{T(n)=\Omega(n^2).}$$

Combining the upper and lower bounds,

$$\boxed{T(n)=\Theta(n^2).}$$

​​