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 - 2)$,

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

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

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 + 2)\lg(n + 2)$,

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

where the last step holds for $n \ge \frac{2c}{1 - c}$, $0 \le c < 1$.

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)$,

$$ \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) + c(n / 2 - 2)\lg(n / 2 - 2) + 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} + dn \\ & = c(n - 2)\lg\frac{n - 2}{2} + dn \\ & = c(n - 2)\lg(n - 2) - c(n - 2) + dn \\ & = c(n - 2)\lg(n - 2) + (d - c)n + 2c \\ & \le c(n - 2)\lg(n - 2), \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)$,

$$ \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) + c(n / 2-1+2)\lg(n / 2-1+2) + dn \\ & \ge c(n / 2 + 1 )\lg(n / 2 + 1) + c(n / 2 + 1)\lg(n / 2 + 1) + dn \\ & \ge c\frac{n + 2}{2}\lg\frac{n + 2}{2} + c\frac{n + 2}{2}\lg\frac{n + 2}{2} + dn \\ & = c(n + 2)\lg\frac{n + 2}{2} + dn \\ & = c(n + 2)\lg(n + 2) - c(n + 2) + dn \\ & = c(n + 2)\lg(n + 2) + (d - c)n - 2c \\ & \ge c(n + 2)\lg(n + 2), \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 + 1 + 17 - a)\lg(n / 2 + 1 + 17 - a) + n \\ & = c(n + 36 - 2a)\lg\frac{n + 36 - 2a}{2} + n \\ & = c(n + 36 - 2a)\lg(n + 36 - 2a) - c(n + 36 - 2a) + n & (c > 1, n > n_0 = f(a))\\ & \le c(n + 36 - 2a)\lg(n + 36 - 2a) & (a \ge 36) \\ & \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^2$ 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.

I think this question is wrong. According to the master theorem, the solution to the recurrence $T(n) = 4T(n / 2) + n^2$ should be $T(n) = \Theta(n^2\log n)$.

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} $$