# time complexity [duplicate]

$$T(n)=\sqrt{n}T(\sqrt{n})+n$$

$$T(1)=T(2)=1$$

the answer is given as $$\Theta(n\log \log n)$$ I tried to draw recursion tree, it got all crazy

I tried using substitution method instead $$\sqrt{n}=2^{m}$$ $$T(2^{m})=2^{m/2}T(2^{m})+2^{m}$$ $$S(m)=\frac{m}{2}S(m)+m$$ $$\frac{S(m)}{m}=\frac{1}{2}S(m)+1$$ am I right?

## marked as duplicate by Raphael♦Sep 15 '14 at 10:12

• @D.W. Though I don't completely agree with a blanket restriction against "Check my answer" posts, that's just my opinion. Suppose, though, that the OP had said something along the lines of "Here's my attempt at at using substitution ... $S(m)=(2m)/(m+2)$ which doesn't seem at all right. Can anybody point out where I went awry?" That would have been a post where the OP demonstrated some effort, which is what we want. Would such a post have gotten a better reception? – Rick Decker Sep 13 '14 at 20:17
In the second line of your solution, you shouldn't have two terms $T(2^m)$. Here's a correct derivation: \begin{align} T(n) &= \sqrt{n}\ T(\sqrt{n}) + n & \text{so, dividing by n we get}\\ \frac{T(n)}{n} &= \frac{T(\sqrt{n})}{\sqrt{n}} + 1 &\text{and letting n = 2^m we have}\\ \frac{T(2^m)}{2^m} &= \frac{T(2^{m/2})}{2^{m/2}} + 1 \end{align} Now let \begin{align} S(m) &= \frac{T(2^m)}{2^m} & \text{so our original recurrence becomes}\\ S(m) &= S(m/2)+1 \end{align} which is a well-known recurrence with solution $$S(m)=\Theta(\lg m)$$ Returning to $T()$ we then have, with $n=2^m$ (and $m=\lg n$), $$\frac{T(n)}{n} = \Theta(\lg\,\lg n)$$ So $T(n) =\Theta(n\,\lg\,\lg n)$.