算法导论4.5-主方法

算法导论练习4.5-1
对下列递归式，使用主方法求出渐进紧缺界:

$T(n) = 2T(n/4) + 1$

$T(n) = 2T(n/4) + \sqrt{n}$

$T(n) = 2T(n/4) + n$

$T(n) = 2T(n/4) + n^2$

Answer：

$\Theta(n^{\log_4{2}}) = \Theta(\sqrt{n})$

$\Theta(n^{\log_4{2}}\lg{n}) = \Theta(\sqrt{n}\lg{n})$

$\Theta(n)$

$\Theta(n^2)$