How do you prove that $\log n \cdot \log n$ grows no faster than $\sqrt{n}$

Question

I had to graph it to see it. How can I prove it?

Answer 1

Before proving it let us examine the following inequality: $$\log x \le x.$$ It holds for any $x$. Now substitute $x$ to $x^{1/8}$ then we have $$\log x \le 8 x^{1/8}.$$

Now the proof is direct: you can see that $\log^2{n} / \sqrt{n}\le 64/n^{1/4}$ for any $n$.

Answer 2

Suppose we establish that $\log(x)<x$. This is quite trivial. Now let $x=y^{1/n}$,

$$\frac1n\log(y)=\log(y^{1/n})<y^{1/n}$$

$$\log(y)<ny^{1/n}$$

Square both sides.

$$\log^2(y)<n^2y^{2/n}=\mathcal O(y^{2/n})$$

Let $n>4$ and we are done.

Answer 3

What is true is more general: for any $\alpha,\beta>0$, $\;\ln^{\alpha} x=o(x^\beta)\;$ near $\;\infty$.

This is easily deduced from the basic case $\alpha=\beta=1$, or directly proved showing that, if $x$ is large enough, $$\ln x < x^{\tfrac{\beta}{2\alpha}}$$ (compare the derivatives of both sides of the inequality, and use a corollary of the mean-value theorem).