$$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)}$.

  • 2
    $\begingroup$ The equation doesn't make sense when $n=1$ $\endgroup$ – Eric Naslund Jan 15 '16 at 19:48
  • $\begingroup$ Alright. Edited, so it makes sense at $n=1$, but I don't think it matters when trying to find the upper bound? $\endgroup$ – 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 $$

| cite | improve this answer | |
  • $\begingroup$ lol give me a while to understand your answer ^_^" $\endgroup$ – TakamaruTaihou Jan 15 '16 at 22:41
  • $\begingroup$ It seems to be a good answer... but I think that book wanted to find the answer in a different way. It seems to ask for a "guess and confirm" method. $\endgroup$ – TakamaruTaihou Jan 16 '16 at 0:23
  • $\begingroup$ @TakamaruTaihou You're right. But I couldn't have guessed that :) $\endgroup$ – Jack's wasted life Jan 16 '16 at 0:26
  • $\begingroup$ Thanks for the answer though! I at least understand that the book is correct now :\ $\endgroup$ – TakamaruTaihou Jan 16 '16 at 0:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.