$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.
Asked By : Xin
Answered By : Luke Mathieson
For every $c > 0$, there exists $n_{0} geq 0$ and $k geq 0$ such that $log n leq kcdot 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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/41588