Solving recurrence equation by substituion

Question

I am trying to solve T(n) = sqrt(n)*T(sqrt(n))+sqrt(n) by drawing a reccurence tree and solving it be the substitution method. But I am having a hard time wrapping my head around how the sqrt method will affect this process and I am looking for some pointers if possible

Much appreciated!

Answer 1

You can write T(n) = sqrt(n)⋅T(sqrt(n)) + sqrt(n) as

T(n) = n1/2 + n3/4 + n7/8 + ...

We know Σi=1,...,∞ 2-i = 1, so you can say

T(n) = n1/2 + n3/4 + n7/8 + ... < n + n + n + ...

Now you only have to compute the length of the sum by solving n2-x < 2 and you get something like x ≈ log log n.

So the solution is T(n) = O(n ⋅ log log n).

Sorry, you was looking for a solution using the substitun method. I never done this so I read a discription on this site.

Let T(sqrt(n)) = k ⋅ sqrt(n) ⋅ log log sqrt(n) + O(sqrt(n)) for constant k.

T(n) = sqrt(n) ⋅ k ⋅ sqrt(n) ⋅ log log sqrt(n) + sqrt(n) + O(sqrt(n)) 
     = k ⋅ n ⋅ log (0.5 log n) + sqrt(n) + O(sqrt(n))
     = k ⋅ n ⋅ log log n + log 0.5 + sqrt(n) + O(sqrt(n))
     = k ⋅ n ⋅ log log n + O(sqrt(n))
     = O(n log log n)

I hope this helps.