Time Complexity of T(n) = 2 * sqrt(n) * T(sqrt(n)) + c*lgn [closed]

Question

Closed. This question does not meet Stack Overflow guidelines. It is not currently accepting answers.

---

This question does not appear to be about programming within the scope defined in the help center.

Closed 8 years ago.

Improve this question

I have been trying to solve this question but I could not find anything.

My approach:

n=2^k then S(k) = k * S(k/2) + c*k

Now, I dont know what to do next. Do you have any ideas?

Answer 1

If you try to write it down for several recursion cycles, you get this :

2*n^(1/2) [2*n^(1/4) (2*n^(1/8) . T(n^(1/16) + c log n) + c log n] + c log n

If you try to count it, it would be (assymptoticaly) :

2^log n * n^(1/2 + 1/4 + 1/8 + ... + 1/log n) + 2^(log n) * n(1/2 + 1/4 + 1/8 + ... + 1/log n) * c * log n

By sumation of series and thanks to that 2^log_2 n = n you get (assymptoticaly) :

n^2 + c * n^2 * log n

Which actually is assymptoticaly : n^2(1 + c * log n) = n^2(c * log n) = n^2 * c * log n

Result : T(n) = O(c * n^2 * log n)