给定

$T(n)=\begin{cases}1,&n=1\\a T(\dfrac{n}{b})+f(n),&\text{otherwise}\end{cases}$

试计算$T(n)$。

令$c_{crit}=\log_ba$：

• 若$f(n)=O(n^c)$且$c
• 若$\exists k$使得$f(n)=n^{c_{crit}}\log^kn$，则有：$T(n)=\begin{cases}\Theta(n^{c_{crit}}\log^{k+1}n),&k>-1\\\Theta(n^{c_{crit}}\log\log n),&k=-1\\\Theta(n^{c_{crit}}),&k<-1\end{cases}$
• 若$f(n)=\Omega(n^c)$且$c>c_{crit}$则有$T(n)=\Theta(f(n))$