CC BY 4.0 （除特别声明或转载文章外）
如果这篇博客帮助到你，可以请我喝一杯咖啡~
求证：master theorem 的 Case 3，即当 $a>b^d$ 时有
\[T(n)=cn^d\sum_{t=0}^{\log_bn}\left(\frac{a}{b^d}\right)^t\\ =\Theta\left(n^d\left(\frac{a}{b^d}\right)^{\log_bn}\right)\\ =\Theta\left(n^{\log_ba}\right)\]
证明：第一个等号已经在前两个 Case 中证明，下面分别证明后两个等式。
带入 $x_1=cn^d ,q=\frac{a}{b^d}, m=1+\log_bn$ 到等比数列求和公式 $S\left(m\right)=x_1\frac{q^m-1}{q-1}$，有
\[T\left(n\right)=S\left(m\right)\\ =x_1\frac{q^m-1}{q-1}\\ =x_1\left(\frac{q^m}{q-1}-\frac{1}{q-1}\right)\\ =x_1\left(\frac{q}{q-1}q^{m-1}-\frac{1}{q-1}\right)\]由于 $\frac{q}{q-1}, \frac{1}{q-1}$ 均为常数，记常数 $c’=\frac{q}{q-1}=1+\frac{1}{q-1}$，则有
\[T\left(n\right)=x_1\left(\frac{q}{q-1}q^{m-1}-\frac{1}{q-1}\right)\\ =x_1\left(c'q^{m-1}-c'+1\right)\\ =x_1\left[c'\left(q^{m-1}-1\right)+1\right]\\ =\Theta(x_1\left[c'\left(q^{m-1}-1\right)+1\right])\]由于 $a>b^d$ ，因此 $q=\frac{a}{b^d}>1, \lim_{m\to\infty}q^{m-1}=\infty\gg 1$。同时 $c,c’$ 均为常数，则有
\[T\left(n\right)=\Theta(x_1\left[c'\left(q^{m-1}-1\right)+1\right])\\ =\Theta(x_1q^{m-1})\\ =\Theta\left(cn^d\left(\frac{a}{b^d}\right)^{\log_bn}\right)\\ =\Theta\left(n^d\left(\frac{a}{b^d}\right)^{\log_bn}\right)\]于是我们证明了第二个等号，接下来证明第三个等号。
\[T\left(n\right)=\Theta\left(n^d\left(\frac{a}{b^d}\right)^{\log_bn}\right)\\ =\Theta\left(n^da^{\log_bn}\left({b^{-d}}\right)^{\log_bn}\right)\\ =\Theta\left(n^da^{\log_bn}\left({b^{\log_bn}}\right)^{-d}\right)\\ =\Theta\left(n^da^{\log_bn}n^{-d}\right)\\ =\Theta\left(a^{\log_bn}\right)\\ =\Theta\left(\left(n^{\log_na}\right)^{\log_bn}\right)\\ =\Theta\left(n^{\log_ba}\right)\]证毕。
假设 $T(n)=2\cdot T(\frac{n}{2})+32\cdot n$，下面的过程错在哪？
- Inductive Hypothesis: $T\left(n\right)=O\left(n\log n\right)$
- Base case: $T\left(2\right)=2=O\left(1\right)=O\left(2\log 2\right)$
- Inductive Step:
- Suppose that $\forall n<k,T\left(n\right)=O\left(n\log n\right) $.
- Then $T\left(k\right)=2\cdot T\left(\frac{k}{2}\right)+32\cdot k$ by definition.
- So $T\left(k\right)=2\cdot O\left(\frac{k}{2}log\frac{k}{2}\right)+32\cdot k$ by induction.
- But that’s $T\left(k\right)=O\left(k\log k\right)$, so the I.H. holds for $n=k$.
- Conclusion: By induction, $\forall n,T\left(n\right)=O\left(n\log n\right)$.
Inductive Step 的第 4 步错了，该步骤中不能使用 $T\left(k\right)=O\left(k\log k\right)$ 这一论据，因为第一步中的假设成立条件是 $\forall n<k$。换言之，该步骤将需要证明的内容直接作为论据了。
实际上由 master theorem ，$b=2,d=1,a=2=b^d$，应有 $T\left(n\right)=O\left(n^d\log n\right)=O\left(n^2\log n\right)$。