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