26
$\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$
  • 7
    $\begingroup$ Hint: consider $$\lim_{n \to \infty} \frac{\log n}{\sqrt{n}}.$$ $\endgroup$ – Antonio Vargas May 16 '12 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 '12 at 4:08
57
$\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}$.

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

| cite | improve this answer | |
$\endgroup$
5
$\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$).

| cite | improve this answer | |
$\endgroup$
-3
$\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.

| cite | improve this answer | |
$\endgroup$

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.