Little $o$ and Big $O$ notations

Question

I see frequently the notations $f=o(g)$ and $f=O(g)$ (also in the wikipedia) and I can understand their meaning. The thing I somehow do not understand is why the equality $=$ is used and not the symbol "belongs to", $f\in o(g)$ or $f\in O(g)$ ?The notations $o(g)$ , $O(g)$ are sets of functions, are not they?... Thanks.

Answer 1

We can read in the classic Asymptotic Methods in Analysis by N.G. De Bruijn:

• The common interpretation of all these formulas can be expressed as follows. Any expression involving the $O$-symbol is to be considered as a class of functions. ... Sometimes the left-hand-side of a relation is not a class, but a single function, ... Then the relation means that the function on the left is a member of the class on the right.

• It is obvious that the sign $=$ is really the wrong sign for such relations, because it suggests symmetry, and there is no such symmetry. For example $O(x)=(x^2)\ (x\to\infty)$ is correct, but $O(x^2)=O(x) \ (x\to\infty)$ is false. Once this warning has been given, there is, however, not much harm in using the sign $=$, and we shall maintain it, for no other reason than that it is customary.

The phrase ... than that it is customary ... indicates tradition as reason for this somewhat peculiar misuse of notation. This is nicely explained in section 9.2, p. 446 of Concrete Mathematics by R.L. Graham, D.E. Knuth and O. Patashnik.