Editing Big O notation (section)

== History (Bachmann–Landau, Hardy, and Vinogradov notations) ==

The symbol O was first introduced by number theorist [[Paul Bachmann]] in 1894, in the second volume of his book ''Analytische Zahlentheorie'' ("[[analytic number theory]]").<ref name=Bachmann>{{cite book |first=Paul |last=Bachmann |author-link=Paul Bachmann |title=Analytische Zahlentheorie |trans-title=Analytic Number Theory |language=de |volume=2 |location=Leipzig |publisher=Teubner |date=1894 |url=https://archive.org/stream/dieanalytischeza00bachuoft#page/402/mode/2up}}</ref> The number theorist [[Edmund Landau]] adopted it, and was thus inspired to introduce in 1909 the notation o;<ref name="Landau">{{cite book |last=Landau |first=Edmund |author-link=Edmund Landau |url=https://archive.org/details/handbuchderlehre01landuoft |title=Handbuch der Lehre von der Verteilung der Primzahlen|volume=1 |date=1909 |publisher=B. G. Teubner |location=Leipzig |page=61 |language=de |trans-title=Handbook on the theory of the distribution of the primes}} Also see page 883 in vol. 2 of the book (not available from the link given). </ref> hence both are now called Landau symbols. These notations were used in applied mathematics during the 1950s for asymptotic analysis.<ref>{{cite book |title=Asymptotic Expansions |last=Erdelyi |first=A. |year=1956 |publisher=Courier Corporation |isbn=978-0-486-60318-6}}.</ref>
The symbol <math>\Omega</math> (in the sense "is not an ''o'' of") was introduced in 1914 by Hardy and Littlewood.<ref name="HL" /> Hardy and Littlewood also introduced in 1916 the symbols <math>\Omega_R</math> ("right") and <math>\Omega_L</math> ("left"),<ref name="HL2" />  precursors of the modern symbols <math>\Omega_+</math> ("is not smaller than a small o of") and <math>\Omega_-</math> ("is not larger than a small o of"). Thus the Omega symbols (with their original meanings) are sometimes also referred to as "Landau symbols". This notation <math>\Omega</math> became commonly used in number theory at least since the 1950s.<ref name="titchmarsh">E. C. Titchmarsh, The Theory of the Riemann Zeta-Function (Oxford; Clarendon Press, 1951)</ref>

The symbol <math>\sim</math>, although it had been used before with different meanings,<ref name=Wild/> was given its modern definition by  Landau in 1909<ref>{{cite book |first=Edmund |last=Landau |author-link=Edmund Landau |title=Handbuch der Lehre von der Verteilung der Primzahlen |publisher=B. G. Teubner |date=1909 |location=Leipzig |trans-title=Handbook on the theory of the distribution of the primes |language=de |page=62 | url=https://archive.org/details/handbuchderlehre01landuoft}}</ref> and by Hardy in 1910.<ref name=Hardy>{{cite book | first=G. H. | last=Hardy | author-link=G. H. Hardy | title=Orders of Infinity: The 'Infinitärcalcül' of Paul du Bois-Reymond | date=1910 |page=2| url=https://archive.org/details/ordersofinfinity00harduoft | publisher=[[Cambridge University Press]]}}</ref> Just above on the same page of his tract Hardy defined the symbol <math>\asymp</math>, where <math>f(x)\asymp g(x)</math> means that both <math>f(x)=O(g(x))</math> and <math>g(x)=O(f(x))</math> are satisfied. The notation is still currently used in analytic number theory.<ref>{{cite book |last1=Hardy |first1=G. H. |last2=Wright |first2=E. M. |author-link2=E. M. Wright |others=Revised by [[Roger Heath-Brown|D. R. Heath-Brown]] and [[Joseph H. Silverman|J. H. Silverman]], with a foreword by [[Andrew Wiles]]|title=An Introduction to the Theory of Numbers |edition=6th |publisher=Oxford University Press |location=Oxford |year=2008 |orig-year=1st ed. 1938 |isbn=978-0-19-921985-8|chapter=1.6. Some notations}}</ref><ref name=GT>Gérald Tenenbaum, Introduction to analytic and probabilistic number theory, « Notation », page xxiii. American Mathematical Society, Providence RI, 2015.</ref> In his tract Hardy also proposed the symbol <math>\mathbin{\,\asymp\;\;\;\;\!\!\!\!\!\!\!\!\!\!\!\!\!-}</math>, where <math>f \mathbin{\,\asymp\;\;\;\;\!\!\!\!\!\!\!\!\!\!\!\!\!-} g</math> means that <math> f\sim Kg </math> for some constant <math>K\not=0</math>.

In the 1970s the big O was popularized in computer science by [[Donald Knuth]], who proposed the different notation <math>f(x)=\Theta(g(x))</math> for Hardy's <math>f(x)\asymp g(x)</math>, and proposed a different definition for the Hardy and Littlewood Omega notation.<ref name="knuth" />

Two other symbols coined by Hardy were (in terms of the modern ''O'' notation)
:<math> f \preccurlyeq g\iff f = O(g) </math> &nbsp; and &nbsp; <math> f\prec g\iff f = o(g); </math>

(Hardy however never defined or used the notation <math>\prec\!\!\prec</math>, nor <math>\ll</math>, as it has been sometimes reported).
Hardy introduced the symbols <math>\preccurlyeq </math> and <math>\prec </math> (as well as the already mentioned other symbols) in his 1910 tract "Orders of Infinity", and made use of them only in three papers (1910–1913). In his nearly 400 remaining papers and books he consistently used the Landau symbols O and o.

Hardy's symbols <math>\preccurlyeq</math> and <math>\prec</math> (as well as <math>\mathbin{\,\asymp\;\;\;\;\!\!\!\!\!\!\!\!\!\!\!\!\!-}</math>) are not used anymore. On the other hand, in the 1930s,<ref>See for instance "A new estimate for ''G''(''n'') in Waring's problem" (Russian). Doklady Akademii Nauk SSSR 5, No 5-6 (1934), 249–253. Translated in English in: Selected works / Ivan Matveevič Vinogradov; prepared by the Steklov Mathematical Institute of the Academy of Sciences of the USSR on the occasion of his 90th birthday. Springer-Verlag, 1985.</ref> the Russian number theorist  [[Ivan Matveyevich Vinogradov]]  introduced his notation	<math>\ll</math>, which  has been increasingly used in number theory instead of  the <math>O</math> notation. We have
:<math> f\ll g \iff f = O(g), </math>
and frequently both notations are used in the same paper.

The big-O originally stands for "order of" ("Ordnung", Bachmann 1894), and is thus a Latin letter. Neither Bachmann nor Landau ever call it "Omicron". The symbol was much later on (1976) viewed by Knuth as a capital [[omicron]],<ref name="knuth" /> probably in reference to his definition of the symbol [[Omega]]. The digit [[0|zero]] should not be used.