# How to Show $\log n = O(\sqrt{n})$

I am trying to solve this issue but I do not know how to handle the division by $O(\sqrt{n})$.

Prove the following using limits and L’Hôpital’s Rule: That $\log n$ is $O(\sqrt{n})$.

\begin{align*} \lim_{n \rightarrow \infty}\frac{\log n}{\sqrt{n}} &= \lim_{n \rightarrow \infty}\frac{\log n}{10^{1/2 \log n}}\\ \end{align*}

-
I am trying to read this issue but I can't. Also, it doesn't seem like provability is the right tag. –  Lord_Farin Oct 23 '12 at 16:40
I have formatted your question using $\LaTeX$. Please make sure I haven't changed your intended meaning, and also consider learning some basic commands to help render your questions on this site. –  Austin Mohr Oct 23 '12 at 16:50
In fact, $\,\log n=\cal O(n^\epsilon)\,$ , for any $\,\epsilon >0\,$ –  DonAntonio Oct 23 '12 at 18:12
Actually $\log x < \sqrt x$ for all $x>0$. –  lhf Oct 23 '12 at 18:23
Let $a>0$. Then $$\lim_{x\to\infty}\frac{\log x}{x^a}=0$$ –  Pedro Tamaroff Oct 23 '12 at 19:10

Try using L'Hospital's rule:

$\log_{10} n = \frac{\ln(n)}{\ln(10)}$, and let's call $k = 1/\ln(10)$. Then, derivative of the top is $k/n$ and of the bottom is $\frac{1}{2}x^{-1/2} = \frac{1}{2\sqrt{x}}$. By L'Hospital's Rule,

$\lim_{n \to \infty} \frac{\log n}{\sqrt{n}} =\lim_{n \to \infty} \frac{k/n}{\frac{1}{2\sqrt{n}}} =\lim_{n \to \infty} \frac{2k\sqrt{n}}{n} = 0$,

so indeed $\log n = O(\sqrt{n})$.

-
Your proof shows $\log n = o(\sqrt{n})$, which is actually stronger than $\log n = O(n)$. –  Austin Mohr Oct 23 '12 at 17:57
Where did that $k$ come from? –  Pedro Tamaroff Oct 23 '12 at 19:02
@AustinMohr Agree, but the last statement was only for what was asked for in the question... –  gt6989b Oct 23 '12 at 20:42
@PeterTamaroff $k$ is defined in the answer as $1/\ln(10)$, which shows up if you interpret $\log x = \log_{10} x$, as the author of the question had done (instead of $\log x = \ln x$) –  gt6989b Oct 23 '12 at 20:44

You need to prove that $\log x \le c \sqrt x$ for some $c>0$ and for $x$ sufficienty large.

Consider $f(x)=\sqrt x - \log x$. Then $f'(x)=\frac{1}{2\sqrt x}-\frac{1}{x}=\frac{\sqrt x -2}{2x}\ge 0$ for $x\ge4$.

Since $f(4)=2-\log 4>0$, we have $f(x)\ge 0$ for $x\ge4$.

-