# Do not understand why log n = O(n^c) (for any c>0) [duplicate]

This question already has an answer here:

Can anyone help me understand this equation?

$\log (n) = O(n^c)$ (for any $c>0$)

Does it mean that $O(\log (n)) < O(n^c)$ (for any $c>0$)?

Added:

Please also prove that $\log (n) = O(n^c)$ is true.

## marked as duplicate by David Richerby, Juho, D.W.♦, Nicholas Mancuso, Raphael♦Apr 21 '15 at 12:59

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

• You just have to show that logarithms grow slower than polynomials. – Pål GD Apr 20 '15 at 8:28
• Attend the definition. – Raphael Apr 20 '15 at 8:51
• No, it means that, for any $c>0$, there's a constant $k$ such that, for large enough $n$, $\log n < kn^c$. Just like any other statement of the form $f(n)=O(g(n))$. – David Richerby Apr 20 '15 at 10:46

## 1 Answer

It's not actually an equation $f = O(g)$ is a lazy shorthand that should be written $f \in O(g)$. So if you look back at the definition of $O$, you should be able to see what $\log n \in O(n^{c})$ for any $c > 0$ means:

For every $c > 0$, there exists $n_{0} \geq 0$ and $k \geq 0$ such that $\log n \leq k\cdot n^{c}$ for all $n \geq n_{0}$.

Always remember that $O(\cdot)$ describes a set, $O(\log n) < O(n^{c})$ doesn't actually make sense (unless you make up a special meaning for $<$, but then no-one will know what you're talking about). You could say $O(\log n) = O(n^{c})$, as equality for sets has a understood meaning, though of course this statement in particular would be false.

As John Kugelman points out in the comments below, normal set relations do make sense, so $O(f) \subset O(g)$, $O(f) \subseteq O(g)$, etc., make sense.

• $O(\log n) \subset O(n^c)$ is sensible. – John Kugelman supports Monica Apr 20 '15 at 14:31
• Could you add a prove for log(n)=O(n^c), please? – Xin Apr 21 '15 at 4:57
• @Xin the two links in the comments on the question have all the tools you need to work out the proof, have a go, see where you get stuck, walk away from it for a day, try again, then come back and you'll get a lot more out of a more precise question at that point, than just getting someone else's version of the proof now. – Luke Mathieson Apr 21 '15 at 12:46
• @Xin Hint: you won't motivate people to help you if you demonstrate that clearly that you are not interested in understanding but only in having something to hand in tomorrow. – Raphael Apr 21 '15 at 13:00