递推关系T(n)=T(n^1/2)+n的求法

Question

T(n)=T(n^1/4)+n^1/2+n T(n^1/8)+n^1/4+n^1/2+n。。

 T(n^1/2^k)+n^1/k-1+n^1/k-2......+n
 I got k= loglog(n) but i am not able to solve the series by putting this k value into above series.

Answer 1

首先替换n= 2^m给出我们

T( 2^m ) = T(2^(m-1)) +2^m

现在设S(m) = T(2^m)。这极大地简化了递归关系

S(m) = S(m/2) + 2^m

根据主定理，

S(m) = O(2^m)

最后，

T(n) = T(2^m) = S(m) = O(2^m) = O(2^(log_2 n)) =O(N)。