In a research paper I read $F(n) \leq O(g(n))$ and $F(n) \geq \Omega(h(n))$.
Isn't this the same as $F(n) = O(g(n))$ and $F(n) = \Omega(h(n))$?
Is there a difference?
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.Sign up to join this community
The notations $f(n) = O(n)$ and $f(n) \leq O(n)$ mean the same thing. Sometimes want to emphasize that the asymptotic estimate is coarse, and then you can use $\leq$, for example $\log n \leq O(n)$. This is not too common if all you're doing is just stating a single estimate, but is more common in a long calculation in which some steps are equations and some steps are inequalities, for example $$ H_n + 5n = \log n + O(1) + O(n) \leq O(n). $$ In this particular example a simple equality would be more common, but in more complicated situations you could see an inequality. It is up to the authors' personal style. As a reader, you can just ignore this distinction.
I often see
F(n) = O(g(n)), but also
F(n) ∈ O(g(n)).
F(n) ≤ O(g(n)) is a little bit rarer.
All versions mean the same:
F(n) does not grow faster (asymptotically) than
The same holds for the other symbols
What notation is more correct, depends on the definition of the big O Symbol. In most cases
O(g(n)) is defined as a set of all functions that grow not faster than
g(n) (asymptotically), so the the correct way to write it down would be
F(n) ∈ O(g(n)).
But one could define
O also as something like a function (
O: g → f) that turns
g(n) into the function
f(n) with the property that f(n) grows not faster than
g(n) (asymptotically). Then would the notation
F(n) = O(g(n)) be the right. This is sometimes useful, if you want to do something like
F(n)/G(n) = f(n) + o(1), which would make no sense if
o(1) is a set.
I would say
F(n) ≤ O(g(n)) is something we call in Germany "doppelt gemoppelt", which means something like "done twice". The big O means that it grows not faster than, so it includes the "≤" already. But maybe one want it to make it more clear and visible by the first look or something. But you should also check, if the author wants to say something special with this.
I saw a lot people that were struggling with something like
2ⁿ ∈ O(n!) or
log n ∈ O(n⁵). Both is correct, but the bounds are not tight. maybe the author wants to underline that the bound is not tight.