Confusion about Big O notation 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)$?
 A: 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.
