CLRS 4.3用代入法求解递归式

4.3-1
猜测 $\exists c>0$有 $T(n)\leq cn^2$。

$T(n)=T(n-1)+n\leq c(n-1)^2+n=cn^2+(1-2c)n+c$，选 $c=1$有：

$$T(n)\leq n^2-n+1\leq n^2 \quad \text{ for } n \ge 1$$

4.3-2
猜测 $T(n)\leq c\lg{(n-d)}$：

$${ T(n) \leq c \lg {(\lceil \frac {n}{2} \rceil - d)} + 1 \leq c\lg {(\frac {n}{2} -d+1)}+1= c\lg {(n-2d+2)}-c+1\leq c \lg {(n-d)}}$$
其中 $c \ge 1, d \ge 2$。

4.3-3
上界证明书上有，在此省略。
下界证明：
猜测 $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)\lg2 + n \\ &=c(n+2)\lg(n+2) + (1 - c)n - 2c \\ &\ge c(n+2)\lg(n+2) \end{aligned}$$
其中 $n \ge 2c/(1-c), 0 <c<1$
所以 $T(n)=\Theta(n\lg n)$

4.3-4
猜测 $T(n) \le cn\lg n + d$，代入递推式可得

$$\begin{aligned} T(n)&\le 2c \lfloor \frac n2 \rfloor \lg {\lfloor \frac n2 \rfloor} + 2d + n \\ &\le cn\lg {\frac n2} + n + 2d\\ &= cn\lg {n} - (c - 1)n + 2d\\ &\le cn \lg n + d \end{aligned}$$
要让等式成立，就需要 $d-(c-1)n\le 0$，显然要 $c\ge 1$，要保证 $T(1)=1 \le c \cdot 1 \cdot \lg 1 + d = d$，所以 $d \ge 1, c\ge d+1$。

4.3-5
递归式：$T(n) = T(\lfloor n/2 \rfloor) + T(\lceil n/2 \rceil) + \Theta(n)$
证明上界和下界类似，在此就只证明下界。
猜测 $T(n)\ge c(n+d)\lg (n+d)$

$$\begin{aligned} T(n)&\ge c(\lfloor \frac n2 \rfloor+d)\lg (\lfloor \frac n2 \rfloor+d)+c(\lceil \frac n2 \rceil+d)\lg (\lceil \frac n2 \rceil+d)+dn\\ &\ge c(\frac n2 -1+d)\lg (\frac n2-1+d)+c(\frac n2 +d)\lg (\frac n2+d)+dn\\ &\ge 2c (\frac n2 -1+d)\lg (\frac n2-1+d)+dn\\ &=c(n+d+d-2)\lg (n+2d-2)-c(2d-2)+(d-c)n \end{aligned}$$
要使 $c(n+d+d-2)\lg (n+2d-2)-c(2d-2)+(d-c)n\ge c(n+d)\lg (n+d)$，只需 $d\ge 2,0 < c\le d$即可。

4.3-6
猜测 $T(n) \le c (n-d) \lg {(n-d)}$

$$\begin{aligned} T(n)&\le 2c (\lfloor \frac n2 \rfloor +17-d) \lg {(\lfloor \frac n2 \rfloor + 17-d)}+n \\ &\le 2c(\frac n2 +18-d) \lg {(\frac n2 +18-d)} + n \\ &= 2c(\frac n2+18-d) (\lg (n+36-2d) -1)+n \\ &= cn\lg {(n+36-2d)}-(c-1)n-2c(d-18)\lg {(n+36-2d)-2c(d-18)} \end{aligned}$$
要使 $cn\lg {(n+36-2d)}-(c-1)n-2c(d-18)\lg {(n+36-2d)-2c(d-18)}\le cn\lg {(n-d)}$

则需要 $36-d\le 0, c-1 \ge 0, d-18 \ge 0 \Rightarrow c \ge 1, d \ge 36$

4.3-7
猜测 $T(n) \le c n^{\log_3 4}$

$$\begin{aligned} T(n)&\le 4c (\frac n3)^{\log_3 4} + n \\ &= cn^{\log_3 4} + n \end{aligned}$$
证明失败。
猜测 $T(n) \le cn^{\log_3 4} - dn$
$$\begin{aligned} T(n)&\le 4c (\frac n3)^{\log_3 4}-\frac43 dn + n \\ &= cn^{\log_3 4}-dn -(\frac 13 d-1)n \\ \end{aligned}$$
要使 $cn^{\log_3 4}-dn -(\frac 13 d-1)n \le cn^{\log_3 4} -dn$
显然 $\frac 13 d-1\ge 0$即可，所以有 $c \ge 0, d \ge 3$

4.3-8
猜测 $T(n)\le cn^2$

$$T(n) \le 4c(n/2)^2 + n \leq cn^2 + n$$
证明失败。
猜测 $T(n) \le cn^2-dn$
$$\begin{aligned} T(n)&\le 4c(\frac n2)^2 - 4d \frac n2 + n \\ &= cn^2 -dn-(d-1)n \\ &\le cn^2-dn \end{aligned}$$
显然 $c\ge0, d \ge 1$即可。

4.3-9
$T(n) = 3T(\sqrt{n}) + \lg{n}$，令 $m = \lg{n}$有：$T(2^m) = 3T(2^{m/2}) + m$。
令 $p=2^m$有$S(p) = 3S(p/2) + p$
猜测 $S(p) \le cp^{\lg{3}} + dp$：

$$\begin{align} S(p) & \le 3\Big(c(p/2)^{\lg{3}} + d(p/2)\Big) + p \\ & \le cp^{\lg{3}} + (\frac{3}{2}d + 1)p \\ &\le cp^{\lg{3}} + dp \end{align}$$
其中 $d \le -2$。
同理可证明 $S(p) \ge cp^{\lg{3}} + dp$（证明略）
$$\begin{align} S(p) & = \Theta(p^{\lg{3}}) \\ T(n) &= \Theta(\lg^{\lg{3}}{n}) \end{align}$$