Big O notation

From Why start at x, y, z

Big \(O\) notation is commonly written as if it were an equality: \[ x^2+7x+53=O(x^2). \] It is not an equality: the left hand side describes a function of \(x\), but the right hand side is...something else. In an attempt to make this more meaningful, some authors have resorted to treating \(O\)-notation as defining a set of functions, and using set membership instead of equality: \[ x^2+7x+53\in O(x^2). \] This does not work either, for expressions like \[ x^2+7x+53=x^2+O(x). \]

The real meaning of this type of expression appears to be as a proxy for wrapping the entire expression in quantifiers and replacing the equality by an inequality: \[ \exists X\in\mathbb{R}^+\ \exists C\in\mathbb{R}^+\ \forall x\in\mathbb{R}^+\ (x>X \Rightarrow x^2+7x+53\le Cx^2). \]

But even with this interpretation you still have to know, from information beyond the expression, what kind of limiting behavior you are studying: the quantification above describes the limiting behavior as \(x\to\infty\), not as \(x\to 0\).

Maybe the simplest solution is to tell students that "=O" is a special combination of symbols, meaningful only as a combination.