4.3 The substitution method for solving recurrences

4.3-1

Use the substitution method to show that each of the following recurrences defined on the reals has the asymptotic solution specified:

a. $T(n)=T(n-1)+n$ has solution $T(n) = O(n^2)$

b. $T(n)=T(n/2)+\Theta(1)$ has solution $T(n)=O(\lg n)$

c. $T(n)=2T(n/2)+n$ has solution $T(n)=O(n\lg n)$.

d. $T(n)=2T(n/2+17)+n$ has solution $T(n) = O(n\lg n)$.

e. $T(n)=2T(n/3)+\Theta(n)$ has solution $T(n)=\Theta(n)$

f. $T(n) = 4T(n/2)+\Theta(n)$ has solution $T(n)=\Theta(n^2)$.

a.

$$ \begin{aligned} \text{ inductive case: } &\cr & \text{assume }T(n')\leq cn'^2 \text{ for all } n_0 \leq n'\leq n\cr T(n)& =T(n-1)+n\cr & \leq c(n-1)^2+n\cr & = cn^2+(1-2c)n+c\cr & \leq cn^2\cr & \text{while the last step holds for }c > \frac{1}{2}\cr \text{base case: } &\cr T(n) & \leq c \leq cn \text{ for all }n \leq n_0 \text{ is true if and only if choose a large enough } n_0\cr \end{aligned} $$

• tips: base case and detail like $\text{ for all } n_0 \leq n'\leq n$ will be omitted in this kind of problems for convenience.

b.

assume $T(n) \leq c\lg n$

$$ \begin{aligned} T(n)&=T(n/2)+c'\cr &\leq c\lg n -c\lg 2 +c'\cr &\leq c\lg n\cr \end{aligned} $$

the last step holds for $c>c'/\lg 2$.

c.

assume $T(n)\leq cn\lg n$

$$ \begin{aligned} T(n) & = 2T(n/2)+n\cr & \leq 2c(n/2)\lg (n/2) +n\cr & = cn\lg n + (1-c\lg 2)n\cr & \leq cn\lg n \end{aligned} $$

the last step holds for $c>1/\lg 2$.

d.

assume $T(n)\leq c(n-a)\lg (n-a)$

$$ \begin{aligned} T(n)&=2T(n/2+17)+n\cr & \leq 2(c(n/2+17-a))\lg(n/2-a+17)+n\cr & = c(n-2a+34)\lg(n -a +34)+(1-c\lg 2)n +c(-2a+34)\lg 2\cr & \leq c(n-a)\lg (n-a)\cr \end{aligned} $$

the last step holds for $n\geq 34$

e. assume $c_{1}n\leq T(n)\leq c_{2}n$

$$ \begin{aligned} T(n) & =2T(n/3)+\Theta(n)\cr & \geq 2(c_{1}n/3)+c_{3}n\cr & =(2c_{1}/3+c_{3})n\cr & \geq c_{1}n\cr \end{aligned} $$

the last step holds for $c_{1}\leq 3c_{3}$

$c_{3}$ is the lowwer bound constant in $\Theta(n)$.

$$ \begin{aligned} T(n) & =2T(n/3)+c_{4}n\cr & \leq (2c_{2}/3+c_{4})n\cr & \leq c_{2}n\cr \end{aligned} $$

the last step holds for$c_{2}\geq 3c_{4}$

$c_{4}$ is the upper bound constant in $\Theta(n)$.

f.

assume $c_{1}n^2 \leq T(n)\leq c_{2}n^2-c_{0}n$

$$ \begin{aligned} T(n) & =4T(n/2)+\Theta(n)\cr & \geq c_{1}n^2+c_{3}n\cr & \geq c_{1}n^2\cr T(n) & =4T(n/2)+\Theta(n)\cr & \leq c_{2}n^2-2c_{0}n+c_{4}n\cr & \leq c_{2}n^2-c_{0}n\cr \end{aligned} $$

the last step holds for $c_{0}\geq c_{4}$

$c_{3}$ is the lowwer bound constant in $\Theta(n)$ and $c_{4}$ is the upper bound constant in $\Theta(n)$.

4.3-2

The solution to the recurrence $T(n) = 4T(n/2) + n$ turns out to be $T(n) = \Theta(n^2)$.Show that a substitution proof with the assumption $T(n) \leq cn^2$ fails. Then show how to subtract a lower-order term to make a substitution proof work.

assume $T(n)\leq cn^2$

$$ \begin{aligned} T(n) & =4T(n/2)+n\cr & \leq cn^2+n\cr \end{aligned} $$

It can not further imply $T(n)\leq cn^2+n$

assume $T(n)\leq c_{1}n^2-c_{2}n$

$$ \begin{aligned} T(n) & =4T(n/2)+n\cr & \leq c_{1}n^2-2c_{2}n+n\cr & \leq c_{1}n^2-c_{2}n\cr \end{aligned} $$

the last step holds for $c_{2}\geq 1$

4.3-3

The recurrence $T(n)=2T(n-1)+1$ has the solution T(n) = O(2^n). Show that a subtitution proof fails with the assumption $T(n)\leq c2^n$, where $c > 0$ is constant. Then show how to subtract a lower-order term to make a substitution proof work.

assume $T(n)\leq c2^{n}$

$$ \begin{aligned} T(n) & =2T(n-1)+1\cr & \leq 2\cdot c2^{n-1}+1\cr & =c2^{n}+1\cr \end{aligned} $$

It can not further imply $T(n)\leq c2^{n}$

assume $T(n)\leq c2^{n}-d$

$$ \begin{aligned} T(n) & =2T(n-1)+1\cr & \leq 2\cdot c2^{n-1}-2d+1\cr & =c2^{n}-d\cr \end{aligned} $$

the last step holds for $d\geq 1$