Confusion about Big O notation

Question

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)$?

Answer 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.