$\sqrt{\log n}$ vs $\log\sqrt{n}$

Question

I have to check if $ \sqrt{ \log(n) } = \theta(\log({\sqrt n}))$.
Following log rules I can write:

$ \sqrt{ \log(n) } = \log(n)^{\frac{1}{2}}$
$\log({\sqrt n)} = \log(n^{\frac{1}{2}}) = \frac{1}{2}\log(n) $

Looking at graphs I can see the $O$ notation is correct but not the $\Omega$. I would appreciate some help at how to disprove this, as I am stuck for quite some time on it.

Thanks in advance

Answer 1

You want to prove that its not true that $\sqrt{\log(n)} = \Omega(\log\sqrt n)$. It is enough to prove that $\frac{\log\sqrt n}{\sqrt{\log n}}$ is unbounded. But this is true, simply because this ratio is $$ \frac{\log\sqrt n}{\sqrt{\log n}} = \frac{\sqrt{\log n}}{2} \to \infty,$$ for $n$ large.

Answer 2

It might be easiest to see what's going on here if you let $n=e^{u^2}$ (with $u\to\infty$). Then $\sqrt{\log n}=u$ while $\log(\sqrt n)={1\over2}u^2$.