# Prove that $\log(n) = O(\sqrt{n})$

How to prove $\log(n) = O(\sqrt{n})$?

How do I find the $c$ and the $n_0$?

I understand to start, I need to find something that $\log(n)$ is smaller to, but I m having a hard time coming up with the example.

• Hint: consider $$\lim_{n \to \infty} \frac{\log n}{\sqrt{n}}.$$ – Antonio Vargas May 16 '12 at 3:56
• @Anson Can you write your own solution and accept it so that this question gets an answer? meta.math.stackexchange.com/questions/1401/… – user17762 May 16 '12 at 4:08

Less sophisticated: $\log(x) < x$ for all $x > 0$ (as is easily seen from its integral representation). Therefore $\log(x) = 2 \log \sqrt{x} < 2 \sqrt{x}$.

• how'd you get $2\sqrt{x}$ – 夢のの夢 Sep 29 '16 at 2:52
• @Yangfan Substitute $x\leftarrow \sqrt{x}$ in $\log(x) < x$. – WimC Sep 29 '16 at 16:26
• Can you explain this for non-math guys but programmers too? Thanks in advance1 – user1767754 Dec 31 '17 at 13:21
• Just replace $x$ with $(\sqrt{x})^2$. The exponent becomes the multiplier of the logarithm. – giusti May 13 '19 at 20:46

You want $c > 0$ and $n_0$ such that $\log n \le c \sqrt{n}$ for $n > n_0$. Actually any $c > 0$ would work, the only problem is to find $n_0$. Alternatively, any $n_0 > 0$ would work if we find the right $c$, and if we have the freedom to choose this might be a better option because it's easier to solve for $c$ than to solve for $n$. The inequality says $c \ge \dfrac{\log n}{\sqrt{n}}$. Note that $$\dfrac{d}{dn} \dfrac{\log n}{\sqrt{n}} = \dfrac{2-\log n}{2 n^{3/2}}$$ so $\log (n)/\sqrt{n}$ is increasing for $n \le e^2$ and decreasing for $n \ge e^2$. Thus we could take $c = \log(e^2)/\sqrt{e^2} = 2/e \approx .7357588824$ which would work for all $n \ge 1$.

$\log(x) < \sqrt{x}$ for all $x>0$ because $\log(x) /\sqrt{x}$ has a single maximum value $2/e<1$ (at $x=e^2$).

consider n=2^100

then log(n)=Log(2^100)

           =100*log2
=100


and now apply this to sqrt(n)

then Sqrt(n)=sqrt(2^100)

           =2^50


we can clearly say that sqrt(n) is larger then logn.