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

1 Answer 1

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$
7
  • $\begingroup$ but this is exactly what I wrote in my question $\endgroup$
    – Yos
    Commented Jun 7, 2017 at 18:22
  • $\begingroup$ @Yos, no, you have divided $\log \sqrt n$ instead of $\sqrt n \log \sqrt n$. $\endgroup$
    – rus9384
    Commented Jun 7, 2017 at 18:23
  • $\begingroup$ but you're getting the same result I got, what does you answer contribute? $\endgroup$
    – Yos
    Commented Jun 7, 2017 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
    Commented Jun 7, 2017 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
    Commented Jun 7, 2017 at 18:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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