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
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.
No comments:
Post a Comment