Solve the following recurrence:
$$\ T(n) = \sqrt{n}\cdot T(\sqrt{n}) + n\cdot \log(n)$$
I tried to just unroll it to see if I can understand, but it is too complicated .
$\ T(n) = n^{\frac{1}{2}} \cdot T(n^{\frac{1}{2}}) +n\cdot \log(n)\\
= n^{\frac{1}{2}} \cdot \left( n^{\frac{1}{4}} \cdot T(n^{\frac{1}{4}} ) + \frac{n}{2} \cdot \log(\frac{n}{2}) \right) + n \cdot \log(n) \\
= n^{\frac{1}{2}} \left( n^{\frac{1}{4}} \cdot \left( n^{\frac{1}{8}} \cdot T(n^{\frac{1}{8}}) + \frac{n}{4}\cdot \log(\frac{n}{4}) \right) + \frac{n}{2} \cdot \log(\frac{n}{2}) \right) + n\cdot \log(n) $
Not really clear how to proceed here? I also tried recurrence tree, but couldn't see a clear pattern. I've found a similar question here but I could not understand the answer
Best Answer
The Ansatz $T(n)\sim An^p\log^qn$ gives$$An^p\log^qn=\frac{A}{2^q}n^{(p+1)/2}\log^qn+n\log n\implies A=2,\,p=q=1.$$