# A questions about the Big $\mathcal{O}$ -notation

In my Analysis textbook, the author writes $$f(x)=\mathcal{O}(g(x))$$

But in a video the person said $$f(x)\in\mathcal{O}(g(x))$$ is the correct interpretation, and even said, the other notation doesnt make any sense.

Is one considered better? Or is one really wrong? Does $$f(x)=\mathcal{O}(g(x))$$ still imply that $$f(x)$$ is an element of a given set?

• Commented Jul 9, 2020 at 20:30

I would say $$f(x) \in \mathcal O(g(x))$$ is technically more correct, but $$f(x) = \mathcal O(g(x))$$ is used a lot in literature. The problem with the notation is that the = sign is not symmetric here, that is, $$f(x) = \mathcal O(g(x))$$ does not mean that $$\mathcal O(g(x)) = f(x)$$; the latter does not even make sense.

The notation $$f(x) = \mathcal O(g(x))$$ is quite convenient I find, since it allows you to manipulate equalities very easily. For instance, if you have $$f_1(x) = \mathcal O(g(x))$$ and $$f_2(x) = \mathcal O(g(x))$$ you can these equalities up to get

$$f_1(x) + f_2(x) = \mathcal O(g(x)) + \mathcal O(g(x)) = \mathcal O(g(x)).$$

This is just one (extremely simple) example among so many.

However, the notation $$f(x) \in \mathcal O(g(x))$$ has the advantage that it reminds you that the function is in a certain class of functions, and that from $$f_1(x) = \mathcal O(g(x))$$ and $$f_2(x) = \mathcal O(g(x))$$ you cannot conclude that $$f_1(x) = f_2(x)$$.

Indeed, $$f(x) = \mathcal O(g(x))$$ means that $$f$$ is a function verifying $$f(x) \leq M g(x)$$ for a certain $$M$$ and for all $$x$$ large enough, but of course such a function is nowhere near unique.

The notation $$f(x)=\mathcal O(g(x))$$ is common in many textbooks and papers, however it violates the axioms for the equivalence relation "$$=$$". For instance, it is true that $$\mathcal O(x)=\mathcal O(x^2)$$ but not that $$\mathcal O(x^2)=\mathcal O(x)$$: The relation "$$=$$" is not symmetric. It is much more instructive to think about $$\mathcal O(g(x))$$ as a class of functions where $$f(x)$$ can be an element, and hence the set notation is better.

Since this abuse of notation is so common you are free to choose either convention in any context!

Formal definition, taking non negative, case is: $$O(g) = \left\lbrace f:\exists C > 0, \exists N \in \mathbb{N}, \forall n (n > N \& n \in \mathbb{N}) (f(n) \leqslant C \cdot g(n)) \right\rbrace$$

So $$O(g)$$ is set of function and, obviously, $$f \in O(g)$$ is correct notation. Using here $$"="$$ is some kind of mathematical slang, sometimes called abuse notation, and is used by a lot of sources. Somebody argued it with easiness of using in transformations. Important is that we must differ $$f = O(g)$$ type records from $$O(f) = O(g)$$ type records, because last is equality between sets. Though many well known sources explain last type of record as "$$\subset$$", i.e. working from left to right, I think it come time to note, that most of well known properties of $$O$$ holds in both directions, as "$$\subset \land \supset$$". Some examples of formal proofs are here