4.3 The substitution method for solving recurrences

4.3-1

Show that the solution of $T(n) = T(n - 1) + n$ is $O(n^2)$.

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

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

where the last step holds for $c > \frac{1}{2}$.

4.3-2

Show that the solution of $T(n) = T(\lceil n / 2 \rceil) + 1$ is $O(\lg n)$.

We guess $T(n) \le c\lg(n - a)$,

$$\begin{aligned} T(n) & \le c\lg(\lceil n / 2 \rceil - a) + 1 \\ & \le c\lg((n + 1) / 2 - a) + 1 \\ & = c\lg((n + 1 - 2a) / 2) + 1 \\ & = c\lg(n + 1 - 2a) - c\lg 2 + 1 & (c \ge 1) \\ & \le c\lg(n + 1 - 2a) & (a \ge 1) \\ & \le c\lg(n - a), \end{aligned}$$

4.3-3

We saw that the solution of $T(n) = 2T(\lfloor n / 2 \rfloor) + n$ is $O(n\lg n)$. Show that the solution of this recurrence is also $\Omega(n\lg n)$. Conclude that the solution is $\Theta(n\lg n)$.

First, we guess $T(n) \le cn\lg n$,

$$\begin{aligned} T(n) & \le 2c\lfloor n / 2 \rfloor\lg{\lfloor n / 2 \rfloor} + n \\ & \le cn\lg(n / 2) + n \\ & = cn\lg n - cn\lg 2 + n \\ & = cn\lg n + (1 - c)n \\ & \le cn\lg n, \end{aligned}$$

where the last step holds for $c \ge 1$.

Next, we guess $T(n) \ge c(n + a)\lg(n + a)$,

$$\begin{aligned} T(n) & \ge 2c(\lfloor n / 2 \rfloor + a)(\lg(\lfloor n / 2 \rfloor + a) + n \\ & \ge 2c((n - 1) / 2 + a)(\lg((n - 1) / 2 + a)) + n \\ & = 2c\frac{n - 1 + 2a}{2}\lg\frac{n - 1 + 2a}{2} + n \\ & = c(n - 1 + 2a)\lg(n - 1 + 2a) - c(n - 1 + 2a)\lg 2 + n \\ & = c(n - 1 + 2a)\lg(n - 1 + 2a) + (1 - c)n - (2a - 1)c & (0 \le c < 1, n \ge \frac{(2a - 1)c}{1 - c}) \\ & \ge c(n - 1 + 2a)\lg(n - 1 + 2a) & (a \ge 1) \\ & \ge c(n + a)\lg(n + a), \end{aligned}$$

4.3-4

Show that by making a different inductive hyptohesis, we can overcome the difficulty with the boundary condition $T(1) = 1$ for recurrence $\text{(4.19)}$ without adjusting the boundary conditions for the inductive proof.

We guess $T(n) \le n\lg n + n$,

$$\begin{aligned} T(n) & \le 2(c\lfloor n / 2 \rfloor\lg{\lfloor n / 2 \rfloor} + \lfloor n / 2 \rfloor) + n \\ & \le 2c(n / 2)\lg(n / 2) + 2(n / 2) + n \\ & = cn\lg(n / 2) + 2n \\ & = cn\lg n - cn\lg{2} + 2n \\ & = cn\lg n + (2 - c)n \\ & \le cn\lg n + n, \end{aligned}$$

where the last step holds for $c \ge 1$.

This time, the boundary condition is

$$T(1) = 1 \le cn\lg n + n = 0 + 1 = 1.$$

4.3-5

Show that $\Theta(n\lg n)$ is the solution to the "exact" recurrence $\text{(4.3)}$ for merge sort.

The recurrence is

$$T(n) = T(\lceil n / 2 \rceil) + T(\lfloor n / 2 \rfloor) + \Theta(n) \tag{4.3}$$

To show $\Theta$ bound, separately show $O$ and $\Omega$ bounds.

• For $O(n\lg n)$, we guess $T(n) \le c(n - 2)\lg(n - 2) - 2c$,

$$\begin{aligned} T(n) & \le c(\lceil n / 2 \rceil -2 )\lg(\lceil n / 2 \rceil - 2) + c(\lfloor n / 2 \rfloor - 2)\lg(\lfloor n / 2 \rfloor - 2) + dn \\ & \le c(n / 2 + 1 - 2)\lg(n / 2 + 1 - 2) - 2c + c(n / 2 - 2)\lg(n / 2 - 2) - 2c + dn \\ & \le c(n / 2 - 1 )\lg(n / 2 - 1) + c(n / 2 - 1)\lg(n / 2 - 1) + dn \\ & = c\frac{n - 2}{2}\lg\frac{n - 2}{2} + c\frac{n - 2}{2}\lg\frac{n - 2}{2} - 4c + dn \\ & = c(n - 2)\lg\frac{n - 2}{2} - 4c + dn \\ & = c(n - 2)\lg(n - 2) - c(n - 2) - 4c + dn \\ & = c(n - 2)\lg(n - 2) + (d - c)n + 2c - 4c \\ & \le c(n - 2)\lg(n - 2) - 2c, \end{aligned}$$

where the last step holds for $c > d$.

• For $\Omega(n\lg n)$, we guess $T(n) \ge c(n + 2)\lg (n + 2) + 2c$,

$$\begin{aligned} T(n) & \ge c(\lceil n / 2 \rceil +2 )\lg(\lceil n / 2 \rceil + 2) + c(\lfloor n / 2 \rfloor + 2)\lg(\lfloor n / 2 \rfloor + 2) + dn \\ & \ge c(n / 2 + 2)\lg(n / 2 + 2) + 2c + c(n / 2 - 1 + 2)\lg(n / 2 - 1 + 2) + 2c + dn \\ & \ge c(n / 2 + 1)\lg(n / 2 + 1) + c(n / 2 + 1)\lg(n / 2 + 1) + 4c + dn \\ & \ge c\frac{n + 2}{2}\lg\frac{n + 2}{2} + c\frac{n + 2}{2}\lg\frac{n + 2}{2} + 4c + dn \\ & = c(n + 2)\lg\frac{n + 2}{2} + 4c + dn \\ & = c(n + 2)\lg(n + 2) - c(n + 2) + 4c + dn \\ & = c(n + 2)\lg(n + 2) + (d - c)n - 2c + 4c \\ & \ge c(n + 2)\lg(n + 2) + 2c, \end{aligned}$$

where the last step holds for $d > c$.

4.3-6

Show that the solution to $T(n) = 2T(\lfloor n / 2 \rfloor + 17) + n$ is $O(n\lg n)$.

We guess $T(n) \le c(n - a)\lg(n - a)$,

$$\begin{aligned} T(n) & \le 2c(\lfloor n / 2 \rfloor + 17 - a)\lg(\lfloor n / 2 \rfloor + 17 - a) + n \\ & \le 2c(n / 2 + 17 - a)\lg(n / 2 + 17 - a) + n \\ & = c(n + 34 - 2a)\lg\frac{n + 34 - 2a}{2} + n \\ & = c(n + 34 - 2a)\lg(n + 34 - 2a) - c(n + 34 - 2a) + n & (c > 1, n > n_0 = f(a)) \\ & \le c(n + 34 - 2a)\lg(n + 34 - 2a) & (a \ge 34) \\ & \le c(n - a)\lg(n - a). \end{aligned}$$

4.3-7

Using the master method in Section 4.5, you can show that the solution to the recurrence $T(n) = 4T(n / 3) + n$ is $T(n) = \Theta(n^{\log_3 4})$. Show that a substitution proof with the assumption $T(n) \le cn^{\log_3 4}$ fails. Then show how to subtract off a lower-order term to make the substitution proof work.

We guess $T(n) \le cn^{\log_3 4}$ first,

$$\begin{aligned} T(n) & \le 4c(n / 3)^{\log_3 4} + n \\ & = cn^{\log_3 4} + n. \end{aligned}$$

We stuck here.

We guess $T(n) \le cn^{\log_3 4} - dn$ again,

$$\begin{aligned} T(n) & \le 4(c(n / 3)^{\log_3 4} - dn / 3) + n \\ & = 4(cn^{\log_3 4} / 4 - dn / 3) + n \\ & = cn^{\log_3 4} - \frac{4}{3}dn + n \\ & \le cn^{\log_3 4} - dn, \end{aligned}$$

where the last step holds for $d \ge 3$.

4.3-8

Using the master method in Section 4.5, you can show that the solution to the recurrence $T(n) = 4T(n / 2) + n$ is $T(n) = \Theta(n^2)$. Show that a substitution proof with the assumption $T(n) \le cn^2$ fails. Then show how to subtract off a lower-order term to make the substitution proof work.

First, let's try the guess $T(n) \le cn^2$. Then, we have

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

We can't proceed any further from the inequality above to conclude $T(n) \le cn^2$.

Alternatively, let us try the guess

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

which subtracts off a lower-order term. Now we have

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

where the last step holds for $c \ge 1 / 2$.

4.3-9

Solve the recurrence $T(n) = 3T(\sqrt n) + \log n$ by making a change of variables. Your solution should be asymptotically tight. Do not worry about whether values are integral.

First,

$$\begin{aligned} T(n) & = 3T(\sqrt n) + \lg n & \text{ let } m = \lg n \\ T(2^m) & = 3T(2^{m / 2}) + m \\ S(m) & = 3S(m / 2) + m. \end{aligned}$$

Now we guess $S(m) \le cm^{\lg 3} + dm$,

$$\begin{aligned} S(m) & \le 3\Big(c(m / 2)^{\lg 3} + d(m / 2)\Big) + m \\ & \le cm^{\lg 3} + (\frac{3}{2}d + 1)m & (d \le -2) \\ & \le cm^{\lg 3} + dm. \end{aligned}$$

Then we guess $S(m) \ge cm^{\lg 3} + dm$,

$$\begin{aligned} S(m) & \ge 3\Big(c(m / 2)^{\lg 3} + d(m / 2)\Big) + m \\ & \ge cm^{\lg 3} + (\frac{3}{2}d + 1)m & (d \ge -2) \\ & \ge cm^{\lg 3} + dm. \end{aligned}$$

Thus,

$$\begin{aligned} S(m) & = \Theta(m^{\lg 3}) \\ T(n) & = \Theta(\lg^{\lg 3}{n}). \end{aligned}$$