Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
4  
Hint: consider $$\lim_{n \to \infty} \frac{\log n}{\sqrt{n}}.$$ –  Antonio Vargas May 16 '12 at 3:56
    
Thank you I just figured that out –  Anson May 16 '12 at 4:06
1  
@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
add comment

3 Answers

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

share|improve this answer
add comment

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

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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