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?

No correct solution

OTHER TIPS

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

enter image description here

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:

enter image description here

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))

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)
Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top