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

Question

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?

Answer 1

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.

Answer 2

Both notations are usually admitted.

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.

Answer 3

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!

Answer 4

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