# Big O Notation “is element of” or “is equal”

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?

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