[Math] How to find the order of growth of this recurrence: $T(n) =\sqrt{n}T\bigl(\sqrt{n}\bigr) + n$

recurrence-relationsrecursion

I am trying to find the order of growth ($O(n)$, $O(n\log n)$) of the recurrence $T(n) = \sqrt{n} \cdot T\bigl(\sqrt{n}\bigr) + n$.

I started to unroll the recurrence and found that I can rewrite it in the form:

$$T(n) = n^{\frac{2^k – 1}{2^k}}\cdot T(n^{\frac{1}{2^k}}) + kn$$

My with the thought of solving the equation $n^{\frac{1}{2^k}} = 1$ in terms of $k$ and thus finding the value of the recurrence.

The problem is that $k = \infty $, which leads me to the thought that I went to the wrong direction.

How can I find the solution for this recurrence.

P.S. I know that the solution is $O(n \cdot \log \log n)$, but I do not want to start with it.

P.S.2 This is not a homework, just trying to refresh my math knowledge for analysis of recurrences in programming.

Best Answer

Thanks to Peter's comment, I found the solution: $T(n) = n^{\frac{2^k - 1}{2^k}}\cdot T(n^{\frac{1}{2^k}}) + kn$.

Using not 1, but 2 as the stopping point: $n^{\frac{1}{2^k}} = 2$, which means that $k = \log \log n$.

Putting it back to the equation: $T(n) = n^{\frac{\log n - 1}{\log n}}\cdot T(2) + n \log \log n$, which means that the order of growth is $O(n \log \log n)$

Related Question