0
$\begingroup$

I'd like to prove that $\sqrt n\log{\sqrt n}=\Theta(n)$ but I'm not sure how to do it.

This is my attempt: $$ \lim_{n \to \infty}\frac{\log{\sqrt n}}{\sqrt n}=0 \Rightarrow \log{\sqrt n}=o(\sqrt n) \text{(Little o)} $$

Therefore: $$ \sqrt n\log{\sqrt n}=o(\sqrt n\cdot \sqrt n)=o(n) $$ But this is too much as I need theta.

$\endgroup$
  • 7
    $\begingroup$ You can't prove it since it's not true. $\endgroup$ – Yuval Filmus Jun 7 '17 at 18:15
  • $\begingroup$ "I calculated 1+1=2, but that's too much as I need 1" -- see the problem here? $\endgroup$ – Raphael Jun 7 '17 at 21:43
1
$\begingroup$

$$\lim_{n\to\infty} \frac{\sqrt n \log\sqrt n}{n} = 0$$

Since this $\Theta(\sqrt n \log \sqrt n) = o(n) < \Theta(n)$.

Two functions $f(x), g(x)$ are asymptotically equal iff

$$\lim_{x\to\infty} \frac{f(x)}{g(x)} = c,\ c \in \mathbb{R},\ c > 0$$

$\endgroup$
  • $\begingroup$ but this is exactly what I wrote in my question $\endgroup$ – Yos Jun 7 '17 at 18:22
  • $\begingroup$ @Yos, no, you have divided $\log \sqrt n$ instead of $\sqrt n \log \sqrt n$. $\endgroup$ – rus9384 Jun 7 '17 at 18:23
  • $\begingroup$ but you're getting the same result I got, what does you answer contribute? $\endgroup$ – Yos Jun 7 '17 at 18:25
  • 2
    $\begingroup$ @Yos, yes, result is the same, because the statement itself is wrong. It would be correct if limit would be finite non-zero. $\endgroup$ – rus9384 Jun 7 '17 at 18:27
  • $\begingroup$ So you should say this explicitly in your answer. Otherwise you're just providing an almost identical calculation and identical result. $\endgroup$ – Yos Jun 7 '17 at 18: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.