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} \]

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用