# Can I prove that $\sqrt n\log{\sqrt n}=\Theta(n)$?

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.

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

$$\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$$

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