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

Question

People are always having trouble with "big $O$" notation when it comes to how to write it down in a mathematically correct way.

Example: you have two functions $n\mapsto f(n) = n^3$ and $n\mapsto g(n) = n^2$

Obviously $f$ is asymptotically faster than $g$. Is it $f(n) = O (g(n))$ or is it $f(n) \in O(g(n))$?

My prof says that the first one is wrong but is a very common practice, therefore it is used very offten in books. Although the second one is the right one.

Why is that so?

Answer 1

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

Answer 2

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

Answer 3

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

Answer 4

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.

Answer 5

Here is my five pennies worth: If we see a statement of the form $$f(x)=g(x)+O\bigl(p(x)\bigr)\qquad(x\to\xi)$$ then for each $x$ the exact value of the term $O\bigl(p(x)\bigr)$ is defined by this very equation: it is $:=f(x)-g(x)$. In addition we are told that there is a constant $C>0$ such that for all $x$ in a suitable punctured neighborhood of $\xi$ this difference is $\leq C\bigl|p(x)\bigr|$.

Answer 6

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

Answer 7

As others have pointed out, the one-way property of membership ($\in$) is, in reality, more appropriate than the implicit, or rather explicit, two-way property of equality ($=$), as it is customarily used in all other mathematical contexts. The entire point of the question is to determine which is correct, not which is currently in use.

Also as others have pointed out, there may be cases where it is inconvenient to combine function notations with $\mathcal{O}()$ notations, such as: $$x^3 + \mathcal{O}(x) = \mathcal{O}(x^3)$$ In this case, here is what I would do: $$\{x^3\} \cup \mathcal{O}(x) \subseteq \mathcal{O}(x^3)$$ This maintains theoretical rigor, which is important, while mirroring the syntax of intuitive usages: $$x^3 + x = \mathcal{O}(x^3)$$

I would also point out that, contrary to the complaints of some answers, using $\mathcal{O}(x^3)$ is not really an abuse of function notation, as "the cube of $x$" is a function on $x$. One could write out $y = x^3$ but that would introduce ambiguity as to whether we are solving for $y$ or $x$. In the same way, you wouldn't write out $\mathcal{O}(g(x) = x^3)$, and if you don't need to use $g$ otherwise, it is simpler and easier to understand $\mathcal{O}(x^3)$.