Search code examples
algorithmrecursioncomplexity-theoryrecurrence

Solving recurrence equation by substituion

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!

Solution

  • 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.