Master theorem
- substitution method
- recursion tree method
- master method
Exercises
Which one of the following is the lowest upper bound of T(n) for the following recursion $T(n)=2T(\sqrt n)+logn$ ? (4分) A
A. $O(lognloglogn)$
B. $O(log^2n)$
C. $O(nlogn)$
D. $O(n^2)$
设 $m = logn$, 则$2^m = n$.
$T(2^m) = 2T(2^{m/2}) + m$
设 $G(m) = T(2^m)$，则原式转化为$G(m) = 2G(m/2) + m$
根据主定理，$a = 2, b = 2, k = 1, p = 0. a = b^k$，满足条件2，所以算法复杂度为$O（mlogm）$
又因为 $m = logn$ ,所以算法复杂度为$O（logn loglogn)$
Reference
https://blog.csdn.net/zju_fish1996/article/details/51074532