4-1（递归式例子）对下列每个递归式，给出T(n)的渐进上界和渐进下界。假定 $n\leq2$n≤2时T(n)时常数。给出尽量紧确的界，并验证其正确性。

不会主方法的先看以下这篇博客：
https://blog.csdn.net/qq_40512922/article/details/96932368

a. $T(n)=2T(n/2)+n^4$T(n)=2T(n/2)+n4

证明：有$a=2,b=2,n^{log_ba}=n$a=2,b=2,nlogb​a=n，$f(n)=f(n^4)=\Omega(n^{\epsilon+1})$f(n)=f(n4)=Ω(nϵ+1)，其中$\epsilon=3$ϵ=3。下面证明正则条件：$\exists c&lt;1,af(n/b)\leq cf(n)$∃c<1,af(n/b)≤cf(n)

$2f(n/2)=\frac{n^4}{8} \leq cn^4$2f(n/2)=8n4​≤cn4

当 $c=1/8$c=1/8时,显然成立。因此$T(n)=\Theta(f(n))=\Theta(n^4)$T(n)=Θ(f(n))=Θ(n4)

---

b. $T(n)=T(7n/10)+n$T(n)=T(7n/10)+n

证明：有$a=1,b=10/7,n^{log_ba}=1$a=1,b=10/7,nlogb​a=1，$f(n)=n=\Omega(n^{\epsilon+0})$f(n)=n=Ω(nϵ+0)，其中$\epsilon=1$ϵ=1，下面证明正则条件：$\exists c&lt;1,af(n/b)\leq cf(n)$∃c<1,af(n/b)≤cf(n)

$f(7n/10)=7n/10 \leq cn$f(7n/10)=7n/10≤cn

当$c=7/10$c=7/10时，显然成立。因此$T(n)=\Theta(f(n))=\Theta(n)$T(n)=Θ(f(n))=Θ(n)

---

c. $T(n)=16T(n/4)+n^2$T(n)=16T(n/4)+n2

证明：有$a=16,b=4,n^{log_ba}=n^2$a=16,b=4,nlogb​a=n2，$f(n)=n^2=\Theta(n^2)$f(n)=n2=Θ(n2)。

因此，$T(n)=\Theta(nlgn)$T(n)=Θ(nlgn)。

---

d. $T(n)=7T(n/3)+n^2$T(n)=7T(n/3)+n2

证明：有$a=7,b=3,n^{log_ba}\approx n^{1.7}$a=7,b=3,nlogb​a≈n1.7，$f(n)=n^2=\Omega(n^{1.7+\epsilon})$f(n)=n2=Ω(n1.7+ϵ)，其中$\epsilon=0.3$ϵ=0.3，下面证明正则条件。

$7f(n/3)=\frac{7n^2}{9} \leq cn^2$7f(n/3)=97n2​≤cn2

当$c=7/9$c=7/9时，显然成立。因此$T(n)=\Theta(f(n))=\Theta(n^2)$T(n)=Θ(f(n))=Θ(n2)

---

e. $T(n)=7T(n/2)+n^2$T(n)=7T(n/2)+n2

证明：有$a=7,b=2,n^{log_ba}\approx n^{2.8}$a=7,b=2,nlogb​a≈n2.8，$f(n)=n^2=O(n^{2.8-\epsilon})$f(n)=n2=O(n2.8−ϵ)，其中$\epsilon=0.8$ϵ=0.8。

因此$T(n)=\Theta(n^{log_ba})=\Theta(n^{log_27})$T(n)=Θ(nlogb​a)=Θ(nlog2​7)

---

f. $T(n)=2T(n/4)+\sqrt n$T(n)=2T(n/4)+n​

证明：有$a=2,b=4,n^{log_ba}=n^{0.5}$a=2,b=4,nlogb​a=n0.5，$f(n)=n^{0.5}=\Theta(n^0.5)$f(n)=n0.5=Θ(n0.5)。
因此，$T(n)=\Theta(f(n)lgn)=\Theta(\sqrt{n}lgn)$T(n)=Θ(f(n)lgn)=Θ(n​lgn)

---

g. $T(n)=T(n-2)+n^2$T(n)=T(n−2)+n2

证明：
$T(n)=\sum_{i=0}^{n}{(2i)^2}=\frac{2n(n+1)(2n+1)}{3}+T(0) = \Theta(n^3)$T(n)=i=0∑n​(2i)2=32n(n+1)(2n+1)​+T(0)=Θ(n3)

---