31
$\begingroup$

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.

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

4 Answers 4

60
$\begingroup$

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}$.

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

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$.

$\endgroup$
6
$\begingroup$

$\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$).

$\endgroup$
-5
$\begingroup$

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.

$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.