Editing Big O notation (section)

=== Big Omega notation ===
<!-- This section is linked from redirects. Please update those links when renaming the section. -->
Another asymptotic notation is <math>\Omega</math>, read "big omega".<ref>{{Cite book|url=https://www.worldcat.org/oclc/676697295|title=Introduction to algorithms|date=2009|publisher=MIT Press|vauthors=Cormen TH, Leiserson CE, Rivest RL, Stein C|isbn=978-0-262-27083-0|edition=3rd|location=Cambridge, Mass.|oclc=676697295|page=48}}</ref> There are two widespread and incompatible definitions of the statement

:<math>f(x)=\Omega(g(x))</math> as <math>x \to a</math>,

where ''a'' is some real number, <math>\infty</math>,  or <math>-\infty</math>, where ''f'' and ''g'' are real functions defined in a neighbourhood of ''a'', and where ''g'' is positive in this neighbourhood.

The Hardy–Littlewood definition is used mainly in [[analytic number theory]], and the Knuth definition mainly in [[computational complexity theory]]; the definitions are not equivalent.

==== The Hardy–Littlewood definition ====
In 1914 [[Godfrey Harold Hardy|G.H. Hardy]] and [[John Edensor Littlewood|J.E. Littlewood]] introduced the new symbol <math>\ \Omega\ ,</math><ref name=HL>{{cite journal |last1=Hardy |first1=G.H. |author1-link=Godfrey Harold Hardy |last2=Littlewood |first2=J.E. |author2-link=John Edensor Littlewood |year=1914 |title=Some problems of diophantine approximation: {{nobr|Part II. The}} trigonometrical series associated with the elliptic {{mvar|θ}}&nbsp;functions |journal=[[Acta Mathematica]] |volume=37 |page=225 |doi=10.1007/BF02401834 |doi-access=free |url=http://projecteuclid.org/download/pdf_1/euclid.acta/1485887376 |url-status=live |access-date=2017-03-14 |archive-url=https://web.archive.org/web/20181212063403/https://projecteuclid.org/download/pdf_1/euclid.acta/1485887376 |archive-date=2018-12-12 }}</ref> which is defined as follows:

:<math> f(x) = \Omega\bigl(\ g(x)\ \bigr) \quad </math> as <math>\quad x \to \infty \quad</math> if <math>\quad \limsup_{x \to \infty}\ \left|\frac{\ f(x)\ }{ g(x) }\right| > 0 ~.</math>

Thus <math>~ f(x) = \Omega\bigl(\ g(x)\ \bigr) ~</math> is the negation of <math>~ f(x) = o\bigl(\ g(x)\ \bigr) ~.</math>

In 1916 the same authors introduced the two new symbols <math>\ \Omega_R\ </math> and <math>\ \Omega_L\ ,</math> defined as:<ref name=HL2>{{cite journal |first1=G.H. |last1=Hardy |author1-link=Godfrey Harold Hardy |first2=J.E. |last2=Littlewood |author2-link=John Edensor Littlewood |year=1916 |title=Contribution to the theory of the Riemann zeta-function and the theory of the distribution of primes  |journal=[[Acta Mathematica]] |volume=41 |pages=119–196 |doi=10.1007/BF02422942 }}</ref>

:<math> f(x) = \Omega_R\bigl(\ g(x)\ \bigr) \quad</math> as <math>\quad x \to \infty \quad</math> if <math>\quad \limsup_{x \to \infty}\ \frac{\ f(x)\ }{ g(x) } > 0\ ;</math>

:<math> f(x)=\Omega_L\bigl(\ g(x)\ \bigr) \quad</math> as <math>\quad x \to \infty \quad</math> if <math>\quad ~ \liminf_{x \to \infty}\ \frac{\ f(x)\ }{ g(x) }< 0 ~.</math>

These symbols were used by [[Edmund Landau|E. Landau]], with the same meanings, in 1924.<ref name=landau>{{cite journal |first=E. |last=Landau |author-link=Edmund Landau |year=1924 |title=Über die Anzahl der Gitterpunkte in gewissen Bereichen.&nbsp;IV. |lang=de |trans-title=On the number of grid points in known regions |journal=Nachr. Gesell. Wiss. Gött. Math-phys. |pages=137–150 }}</ref> Authors that followed Landau,  however, use a different notation for the same definitions:{{citation needed|date=December 2018}} The symbol <math>\ \Omega_R\ </math> has been replaced by the current notation <math>\ \Omega_{+}\ </math> with the same definition, and <math>\ \Omega_L\ </math> became <math>\ \Omega_{-} ~.</math>

These three symbols <math>\ \Omega\ , \Omega_{+}\ , \Omega_{-}\ ,</math> as well as <math>\ f(x) = \Omega_{\pm}\bigl(\ g(x)\ \bigr)\ </math> (meaning that <math>\ f(x) = \Omega_{+}\bigl(\ g(x)\ \bigr)\ </math> and <math>\ f(x) = \Omega_{-}\bigl(\ g(x)\ \bigr)\ </math> are both satisfied), are now currently used in [[analytic number theory]].<ref name=Ivic>{{cite book |first=A. |last=Ivić |author-link=Aleksandar Ivić |year=1985 |title=The Riemann Zeta-Function |at=chapter&nbsp;9 |publisher=John Wiley & Sons }}</ref><ref>{{cite book |first=G. |last=Tenenbaum |author-link=Gérald Tenenbaum |year=2015 |title=Introduction to Analytic and Probabilistic Number Theory |at=§&nbsp;I.5 |publisher=American Mathematical Society |place=Providence, RI }}</ref>

===== Simple examples =====

We have

:<math>\sin x = \Omega(1) \quad</math> as <math>\quad x \to \infty\ ,</math>

and more precisely

:<math> \sin x = \Omega_\pm(1) \quad</math> as <math>\quad x\to\infty ~.</math>

We have

:<math> 1 + \sin x = \Omega(1) \quad</math> as <math>\quad x \to \infty\ ,</math>

and more precisely

:<math> 1 + \sin x = \Omega_{+}(1) \quad</math> as <math>\quad x \to \infty\ ;</math>

however

:<math> 1 + \sin x \ne \Omega_{-}(1) \quad</math> as <math>\quad x \to \infty ~.</math>

==== The Knuth definition ====
In 1976 [[Donald Knuth]] published a paper to justify his use of the <math>\Omega</math>-symbol to describe a stronger property.<ref name="knuth"/> Knuth wrote: "For all the applications I have seen so far in computer science, a stronger requirement ... is much more appropriate". He defined

:<math>f(x)=\Omega(g(x))\Leftrightarrow g(x)=O(f(x))</math>

with the comment: "Although I have changed Hardy and Littlewood's definition of <math>\Omega</math>, I feel justified in doing so because their definition is by no means in wide use, and because there are other ways to say what they want to say in the comparatively rare cases when their definition applies."<ref name="knuth">{{cite journal |first=Donald |last=Knuth |doi-access=free |s2cid-access=free |title=Big Omicron and big Omega and big Theta |journal=SIGACT News |date=April–June 1976 |volume=8 |issue=2 |pages=18–24 |doi=10.1145/1008328.1008329 |s2cid=5230246 }}</ref>