https://whystartat.xyz/index.php?action=history&feed=atom&title=Big_O_notationBig O notation - Revision history2026-05-25T05:05:17ZRevision history for this page on the wikiMediaWiki 1.39.0https://whystartat.xyz/index.php?title=Big_O_notation&diff=71&oldid=prevDavid Eppstein: New article2021-06-30T18:02:25Z<p>New article</p>
<p><b>New page</b></p><div>[[Category:Unpleasantness]]<br />
<br />
Big \(O\) notation is commonly written as if it were an equality:<br />
\[ x^2+7x+53=O(x^2). \]<br />
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:<br />
\[ x^2+7x+53\in O(x^2). \]<br />
This does not work either, for expressions like<br />
\[ x^2+7x+53=x^2+O(x). \]<br />
<br />
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:<br />
\[ \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). \]<br />
<br />
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\).<br />
<br />
Maybe the simplest solution is to tell students that "=O" is a special combination of symbols, meaningful only as a combination.</div>David Eppstein