How to solve the below Recurrence relation?

Question

consider the recurrence equation, provided in the link. This doesn't fit into the form required by the Master Theorem. i don't want to use the substitution method as it is time-consuming. Also i tired by changing the variable (k=2^m), but failed.

How to solve this through recursion tree or iteration method?

 T(n) =n^0.5  T(n^0.5) + n 

p.s : expected solution is : O(nlglgn)

Answer 1

Let U(n) = T(n)/n.

Then U(n) = n^1/2T(n^1/2)/n + 1, and so

U(n) = T(n^1/2)/n^1/2 + 1

U(n) = U(n^1/2) + 1

It's easy enough to find by the iteration method that U(n) <= log log n + U(2), because that's how many times you can take the square root of n before you get to 2 (using log base 2). You could then prove this inductively for all n > 2 if required.

You therefore have T(n) = U(n)*n <= n (log log n + T(2)/2), and that is in O(n log log n)