# What are the rules for equals signs with big-O and little-o?

This question is about asymptotic notation in general. For simplicity I will use examples about big-O notation for function growth as $n\to\infty$ (seen in algorithmic complexity), but the issues that arise are the same for things like $\Omega$ and $\Theta$ growth as $n\to\infty$, or for little-o as $x\to 0$ (often seen in analysis), or any other combination.

The interaction between big-O notation and equals signs can be confusing. We write things like $$\tag{1} 3n^2+4 = O(n^2)$$ $$\tag{2} 5n^2+7n = O(n^2)$$ But we're not allowed to conclude from these two statements that $3n^2+4=5n^2+7n$. Thus it seems that transitivity of equality fails when big-O is involved. Also, we never write things such as $$\tag{3} O(n^2)=3n^2+4,$$ so apparently commutativity is also at risk.

Many textbooks point this out and declare, with varying degrees of indignation, that notations such as $(1)$ and $(2)$ constitute an "abuse of notation" that students are just going to have to get used to. Very well, but then what are the rules that govern this abuse? Mathematicians seem to be able to communicate using it, so it can't be completely random.

One simple way out is to define that the notation $O(n^2)$ properly denotes the set of functions that grow at most quadratically, and that equations like $(1)$ are just conventional abbreviations for $$\tag{4} (n\mapsto 3n^2+4)\in O(n^2)$$ Some authors even insist that writing $(1)$ is plain wrong, and that $(4)$ is the only correct way to express the estimate.

However, other authors blithely write things like $$\tag{5} 5 + O(n) + O(n^2)\log(O(n^3)) = O(n^2\log n)$$ which does not seem to be easily interpretable in terms of sets of functions.

The question: How can we assign meaning to such statements in a principled way such that $(1)$, $(2)$ and $(4)$ are true but $(3)$ is not?

• What's wrong with (5) in terms of sets? It says "The set of functions which are of the form $5+f(n) + g(n) \log h(n)$, where $f \in O(n)$, $g \in O(n^2)$ and $h \in O(n^3)$, is a subset of $O(n^2 \log n)$." Nov 27 '11 at 16:02
• In any case, I recall a good discussion of this in chapter 9 of Concrete Mathematics. Nov 27 '11 at 16:03