How do I solve this recurrence?

51 Views Asked by At

Hello guys I've spent hours on this question and am stuck. I'm not sure how to solve this recurrence.

$$ T(n) = \sqrt{n} \cdot T(\sqrt{n})+n\qquad \text{and} \qquad T(2)=0 $$ For simplicity, assume that  $n=2^{2^k}$ for some $k>0$.

1

There are 1 best solutions below

2
On

Hint

Let $T_n=n\,U_n$ to make $$U(n)=U\left(\sqrt{n}\right)+1$$ which is quite simple to solve