Monday 17 July 2017

logarithms - $sqrt{log n}$ vs $logsqrt{n}$




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

real analysis - How to find $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...