6
$\begingroup$

Which of the following functions grows faster:

$\log{\sqrt{n\log{n}}}$ or $\sqrt{\log{n}}$?

I feel the second one should be the answer, but I find it difficult to prove as the derivatives get very complex. Does anyone know any idea?

$\endgroup$
0

4 Answers 4

3
$\begingroup$

The first is (ignoring very small $n$) greater than $\log (n^{1/2})= \frac12 \log n$.

So setting $a = \log n$ the first is greater than $a/2$ while the latter is $\sqrt{a}$. Whence your intuition was not correct and the first grows faster.

$\endgroup$
0
2
$\begingroup$

For $n >> 1$:

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

Thus the first term grows faster.

$\endgroup$
0
1
$\begingroup$

The first one (blue in the graph) growrs faster

enter image description here

$\endgroup$
0
0
$\begingroup$

First note that if $f(n)$ and $g(n)$ are both positive functions and $$\lim\limits_{n\to\infty}\frac{f(n)}{g(n)}=\infty$$ Then we can say that $f(n)$ grows faster than $g(n)$ as $n$ approaches $\infty$. Symbolically this is written as $f(n)\gg g(n)$. So now we have $$\lim\limits_{n\to\infty}\frac{\log\left(\sqrt{n\log n}\right)}{\sqrt{\log n}}$$ Let $k=\sqrt{\log n}$, then $$\lim\limits_{k\to\infty}\frac{\log\left(\sqrt{e^{k^2}}k\right)}{k}$$ $$=\lim\limits_{k\to\infty}\frac{\log\left(\sqrt{e^{k^2}}\right)+\log k}{k}$$ $$=\lim\limits_{k\to\infty}\frac{\frac12 k^2+\log k}{k}$$ $$=\frac12\lim\limits_{k\to\infty}\frac{k^2+2\log k}{k}$$ $$=\frac12\lim\limits_{k\to\infty}\left(k+\frac{2\log k}{k}\right)=\infty$$ Therefore, as $n\to\infty$, $$\log\left(\sqrt{n\log n}\right) \gg \sqrt{\log n} $$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .