Solving runtime of T(n) = n^(1/2)T(n^(1/2)) + n

Question

I am trying to find the recurrence runtime of the following:

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

But I am unable to find the sum or even an equation that would relate g(n) to the summation of the recurrence. Could someone assist me with the summation?

Answer 1

These type of recursions can be solved by unrolling the recursion, spotting the similarities between elements.

Now at some point the recursion will exhaust itself. This will happen if T(...) = T(a) = b. Any reasonable a will work, so I selected 2. Solving the equation n^(1/2^k) = 2 by taking log of both sides, you get: k = log(log(n)). Now substitute it back in your recursion:

Limit of 2^(-loglogn) is equal to 0 if n -> infinity, so the first element in summation is equal to b. The complexity is O(n * log log (n))

Answer 2

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

    =n^(1/2)[ n^(1/2^2)T(n^(1/2^2)+n^(1/2)]+n

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

    =n^(3/2^2)[n^1/2^3 T(n^(1/2^3)+n^(1/2^3)]+2n

    = and so on 

    assume n^(1/2^k)=2
           1/2^k logn=1
           logn=2k
           log logn = k

   = n^(1-1/2^k)T(n^(1/2^k)+kn
   = n/n(1/2^k)T(2)+kn
   = n/2*2+nloglogn
   =n+nloglogn
   = O(nloglogn)