Big O Notation "is element of" or "is equal"

I really like Wikipedia's note on this:

The statement “$f(x)$ is $O(g(x))$” […] is usually written as $f(x) = O(g(x))$. Some consider this to be an abuse of notation, since the use of the equals sign could be misleading as it suggests a symmetry that this statement does not have. As de Bruijn says, $O(x) = O(x^2)$ is true but $O(x^2) = O(x)$ is not. Knuth describes such statements as “one-way equalities”, since if the sides could be reversed, “we could deduce ridiculous things like $n = n^2$ from the identities $n = O(n^2)$ and $n^2 = O(n^2)$.”

For these reasons, it would be more precise to use set notation and write $f(x) \in O(g(x))$, thinking of $O(g(x))$ as the class of all functions $h(x)$ such that $|h(x)| \leq C|g(x)|$ for some constant $C$. However, the use of the equals sign is customary. Knuth pointed out that “mathematicians customarily use the $=$ sign as they use the word ‘is’ in English: Aristotle is a man, but a man isn't necessarily Aristotle.”


Using $\in$ is set-theoretically correct but inconvenient. For example, $$ \sin x = x - \frac{x^3}{3} + \mathrm O(x^5) $$ In this case $\mathrm O$ should be interpreted as there exists an $\mathrm O(x^5)$ function to make this equality valid. The $=$ notation also allows asymptotic notation to appear on both sides and do arithmetic: $$ e^x + \mathrm O(x) = \mathrm O(e^x) $$ In this case, for every $\mathrm O(x)$ function on the left, there exists an $\mathrm O(e^x)$ function on the right to make this an equality.

Warning: In this case the two sides of $=$ cannot be swapped carelessly. e.g. $\mathrm O(x) = \mathrm O(e^x)$ but $\mathrm O(e^x) \neq \mathrm O(x)$.


$O(g(x))$ is a class of functions - think of it as a "property" functions can have. By the literal interpretation of the equals sign, "$f(x) = O(g(x))$" should be interpreted as "$f$ is literally equal to a certain class of functions." But functions and classes of functions are different sorts of things - even if this was what we meant to say, it's like saying that one particular apple is equal to a basket of apples. But what we mean when we say "$f(x) = O(g(x))$" is that $f$ belongs to the class of functions $O(g(x))$ - so, $f(x) \in O(g(x))$.

The reason we use $=$ instead of $\in$ is because, given the particular uses of big-$O$ notation (and little-$o$ notation, if you're familiar with that) $=$ is massively more convenient. We say things like $x^3 + O(x) = O(x^3)$, for example; we don't mean that $O(x)$ is an object that can actually be added to $x^3$, or that when that addition is done we actually get the class of functions $O(x^3)$, we just mean that for any function $f \in O(x)$, the function $x^3 + f(x)$ is a member of $O(x^3)$. But if I wanted to write that out in more standard notation, I'd have to say something like $\{x^3 + f(x) \mid f(x) \in O(x)\} \subseteq O(x^3)$. This is inconvenient to write and difficult to read, so we prefer the "slicker" notation $x^3 + O(x) = O(x^3)$.

However, I'm not sure I would say that sentences like $f(x) = O(g(x))$ are wrong. By convention, they're perfectly right - it's just that when an expression includes $O$ (or $o$), $=$ does not mean what it usually means. That's okay.


Regarding $=$ being more useful/convenient than $\in$ because of allowing things like $x^3 + O(x) = O(x^3)$, it seems like for that you could use $x^3 + O(x) \subseteq O(x^3)$. This seems more precise to me, because it would mean "every element of the set $x^3 + O(x)$ is an element of the set $O(x^3)$." which is, I think, exactly what one wants to say. (where $g+A:=\{g+f:f\in A\}$ and when $g$ is a function and $A$ is a set of functions, and similarly for similar situations.)

Making the statement with subset is mentioned by Reese's answer, but I think that defining the sum of a function and a set of functions, and also the sum of sets of functions, in the straightforward way removes the inconveniences of saying things like $\{x^3+f(x)∣f∈O(x)\}\subseteq O(x^3)$. (Defining things similarly with multiplication, and application of functions in general.)

When things are defined this way, it should become as simple as using $\in$ instead of $=$ when there is a single function on the left, and using $\subseteq$ instead of $=$ when there is a set of functions on the left, and it seems more precise.


I'll try to clarify wchargin comment.

If you are familiar with Group theory you should not find the $=$ sign awkward. Class of equivalence and quotient spaces usually use the sum notation for doing that.

e.g., $\mathbb{R}/\mathbb{Z}$ elements are usually written as $a+\mathbb{Z}$.

The problem is that big $O$ notation makes implicit use of that, i.e. in the class of $$O(g)=\lbrace f:\exists M,C>0, \forall x_0\geq M: f(x_0)\leq Cg(x_0) \rbrace,$$ as exposed by Clement C.

In this way, $$f=O(g)$$ Means $$f+O(g)=0+O(g)$$ And that is to say than $f\in O(g)$.