2

I have a somewhat stupid question regarding the "Big O" notation: Is there any difference between saying $f=O(g)$ and $f\le O(g)$?

qmaster
  • 63
  • 2
    Did you check the obvious before asking? – Did Feb 07 '15 at 17:35
  • In mathematical analysis we often write $f \leq o(g)$ as a shorthand for the more precise sentence "for some quantity $h=o(g)$, there results $f \leq h$". – Siminore Feb 07 '15 at 17:36
  • @Did I did, but if they are equivalent, why would one use both variants? To me, writing $f=O(g)$ seems to be a lot cleaner and hence my confusion. – qmaster Feb 07 '15 at 17:40
  • @Siminore I don't really understand what you are trying to say, I feel that what you are writing is a tautology. – qmaster Feb 07 '15 at 17:41
  • Well, $O(g)$ is a set, not a single function. So $f \leq O(g)$ is a clear abuse, stronger than $f=O(g)$. – Siminore Feb 07 '15 at 17:42
  • @qmaster Any source for $f\le O(g)$? – Did Feb 07 '15 at 17:43
  • @Did I guess this will come a bit surprising, but it's "The Probabilistic Method" by Alon and Spencer, p. 12, first line. (Only that there we have $|A|\le O(n\ln \delta/\delta)$ for some finite set $A$, and positive integers $n$ and $\delta>10$.) – qmaster Feb 07 '15 at 17:44
  • @Siminore Okay, that makes sense. So actually one should write $f\in O(g)$, but the (already abusive) shorthand is $f=O(g)$ and writing $f\le O(g)$ is just even more abusive. – qmaster Feb 07 '15 at 17:46
  • @qmaster One shouldn't write $f \in O(g)$, since then you can't make sense of expressions like $O(g) + O(h)$. – Yuval Filmus Feb 07 '15 at 17:50
  • @YuvalFilmus Yes, thanks for pointing that out. – qmaster Feb 07 '15 at 17:52
  • This is odd. And the notation seems quite useless. – Did Feb 07 '15 at 17:52
  • @Did On the contrary, it's useful and appears in many places. You can also have something like $O(g)^{O(h)}$, for example. – Yuval Filmus Feb 07 '15 at 17:54
  • Wow... Since it seems necessary to explain the obvious, here we go: (i) The notation $O(\ )$ is useful. (Very.) (ii) The notation $f\leqslant O(g)$ is useless. (Probably even worse.) (iii) The book by Alon and Spencer is marvelous. (Obviously.) – Did Feb 07 '15 at 17:57
  • @YuvalFilmus ??? – Did Feb 07 '15 at 17:57
  • @Did Well, I misunderstood the target of your comment, the result of several conversations taking place in parallel. Of course we all agree on (i),(ii),(iii), though sometimes I also use $f \leq O(g)$, say in the fictitious "$x + O(x^2) \leq x^2 + O(x^2) = O(x^2)$", though the first connective could also have been "$=$". – Yuval Filmus Feb 07 '15 at 17:59
  • In some branches of analysis, it is customary to write $A \leq B \leq C+o(1) \leq D+o(\epsilon)+o(1)$. – Siminore Feb 07 '15 at 18:00

1 Answers1

1

No, these both mean the same thing. Let's assume for simplicity that all functions under consideration are positive. One way to think of big O is that $O(g)$ can stand for any function $h \in \mathcal{O}(g)$, where $\mathcal{O}(g)$ is the class of functions $j$ such that for some constant $C > 0$ and large enough $x$, $h(x) \leq Cg(x)$. The statements $f \leq O(g)$ and $f = O(g)$ translate to $f \leq h$ resp. $f = h$ for some $h \in \mathcal{O}(g)$, both of which are equivalent to $f \in \mathcal{O}(g)$.

In most circumstances, the conventional use is $f = O(g)$ rather than $f \leq O(g)$.

If we want to be more sophisticated, we can say that the statement $f = O(g)$ is shorthand for $$ \exists h \in \mathcal{O}(g) \, f = h. $$ This is the correct interpretation for the right-hand side. The correct interpretation for the left-hand side is existential rather than universal. For example, the (valid) statement $O(f) + O(g) = O(f+g)$ states that $$ \forall h \in \mathcal{O}(f) \forall k \in \mathcal{O}(g) \exists r \in \mathcal{O}(f+g) \, h + k = r. $$ This is (somewhat) similar to the sequent calculus.

Yuval Filmus
  • 57,157