# Finding an upper bound of $T(n) = \sqrt{n} T \left(\sqrt n \right) + n$

$$T(n) = \sqrt{n} T \left(\sqrt n \right) + n, n>1$$ $$T(n) = k, n\le1$$

My book says for upper bound to simplify to

$$T(n) \le \sqrt{n}c\sqrt n\log\left(\sqrt n\right) + n$$ $$= nc\log\left(\sqrt n\right) + n$$ $$= \frac{1}{2}nc\log\left( n\right) + n$$ $$\le cn\log\left(n\right)$$

A few questions here: how does $T(\sqrt n)$ simplify to $c\sqrt n\log\left(\sqrt n\right)$?

Or maybe I'm just asking: How do we know for sure that $T(\sqrt n)\le c\sqrt n\log\left(\sqrt n\right)$?

Also, how does $\frac{1}{2}nc\log\left( n\right) + n$ simplify to $cn\log\left(n\right)$?

By the way, the book says that it assumes that $1\le\frac{1}{2}c\log{(n)}$.

• The equation doesn't make sense when $n=1$ – Eric Naslund Jan 15 '16 at 19:48
• Alright. Edited, so it makes sense at $n=1$, but I don't think it matters when trying to find the upper bound? – TakamaruTaihou Jan 15 '16 at 20:15

We can use the change of variable $a_n=T(2^n)$ to get the recursion $$a_n=2^{n\over2}a_{n\over2}+2^n=2^{{n\over2}+{n\over2^2}}a_{n\over2^2}+2\times2^{n}=2^{{n\over2}+{n\over2^2}+{n\over2^3}}a_{n\over2^3}+3\times2^n =\cdots=2^{n(1-{1\over2^m})}a_{n\over2^m}+m2^n\\ \implies a_{2^m}=2^{2^m-1}a_1+m2^{2^m}\implies a_m=a_{2^{\log_2m}}=2^{m-1}a_1+2^m\log_2m\\ \implies T(m)=a_{\log_2m}={ma_1\over2}+m\log_2\log_2m$$
So a solution to the given recurrence is ($\alpha$ is a constant which equals $T(2)/2$) $$T(n)=\alpha n+n\log_2\log_2n$$ which falls apart at $n\le1$ as pointed out in the comments. Suppose $n\ge2$. Then $\alpha n\le \alpha n\log_2 n$ and $n\log_2\log_2n\le n\log_2n$. Letting $c=1+\alpha$ we have $$T(n)\le cn\log_2n$$