# 高级算法设计与分析-HW1

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

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

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

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

• 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:
1. Suppose that $\forall n<k,T\left(n\right)=O\left(n\log n\right)$.
2. Then $T\left(k\right)=2\cdot T\left(\frac{k}{2}\right)+32\cdot k$ by definition.
3. So $T\left(k\right)=2\cdot O\left(\frac{k}{2}log\frac{k}{2}\right)+32\cdot k$ by induction.
4. 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$。换言之，该步骤将需要证明的内容直接作为论据了。