1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Yes, you are right. Both are equivalent. There is no difference, because O is for upper bound and Omega is for a lower bound. $\endgroup$ – helpYou Jun 19 '15 at 7:50
  • $\begingroup$ Abuse of notation - Big O notation. $\endgroup$ – Dukeling Jun 19 '15 at 11:16
  • $\begingroup$ Do not do this! See also here. $\endgroup$ – Raphael Jul 8 '15 at 8:08
  • 1
    $\begingroup$ Strictly speaking you should write $F \in O(g)$ and $F \in \Omega(h)$. But we all make shortcuts in favour of readability. $\endgroup$ – Pål GD Jul 8 '15 at 14:53
  • $\begingroup$ @Raphael I agree that in an exam, you shouldn't do this. In a research paper, writing $F(n) \leq O(n^2)$ is unlikely to cause any confusion. $\endgroup$ – Pål GD Jul 8 '15 at 14:54
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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 g(n).

The same holds for the other symbols ω (>), Ω (), Θ (=), o (<).

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.

$\endgroup$
  • 1
    $\begingroup$ I would say F(n) ≤ O(g(n)) is more syntactically incorrect than redundant. $\endgroup$ – Dukeling Jun 19 '15 at 11:20
  • $\begingroup$ @Dukeling Depends on how you define between functions. But you are right, that this is not the best way to write it $\endgroup$ – AbcAeffchen Jun 19 '15 at 11:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy