Recursion-tree Master Method_综合

递归表达式

其中, $a >= 1, b > 1$ , $f(n)$ 渐进趋正, 即由渐进分析可知, 存在某个 $n_0 > 0$ , 使得当 $n > n_0$ 时, $f(n)>0$ .

$f(n) = O(n^{\log_b{a}} - \epsilon)$ , for some $\epsilon > 0$

$T(n) = \Theta(n^{\log_b{a}})$ .

$f(n) = \Theta(n^{\log_b{a}} \cdot \lg^{k}n)$ , for some $k >= 0$

$T(n) = \Theta(n^{\log_b{a}} \cdot \lg^{k+1}n)$ .

$f(n) = \Omega(n^{\log_b{a}} + \epsilon)$ , for some $\epsilon > 0$ $and$
$af(n/b) <= (1- \epsilon^{'} ) \cdot f(n)$ for some $\epsilon^{'} > 0$

$T(n) = \Theta(f(n)$ .