Editing Big O notation (section)

=== Family of Bachmann–Landau notations ===
{| class="wikitable"
|-
! Notation
! Name<ref name="knuth" />
! Description
! Formal definition
! Limit definition<ref name=Balcázar>{{cite journal |last1=Balcázar |first1=José L. |last2=Gabarró |first2=Joaquim |title=Nonuniform complexity classes specified by lower and upper bounds |journal=RAIRO – Theoretical Informatics and Applications – Informatique Théorique et Applications |volume=23 |issue=2 |page=180 |url=http://archive.numdam.org/article/ITA_1989__23_2_177_0.pdf |via=Numdam |access-date=14 March 2017 |language=en |issn=0988-3754 |archive-date=14 March 2017 |archive-url=https://web.archive.org/web/20170314153158/http://archive.numdam.org/article/ITA_1989__23_2_177_0.pdf |url-status=live }}</ref><ref name=Cucker>{{cite book |last1=Cucker |first1=Felipe |last2=Bürgisser |first2=Peter |title=Condition: The Geometry of Numerical Algorithms |year=2013 |publisher=Springer |location=Berlin, Heidelberg |isbn=978-3-642-38896-5 |pages=467–468 |chapter=A.1 Big Oh, Little Oh, and Other Comparisons |chapter-url=https://books.google.com/books?id=SNu4BAAAQBAJ&pg=PA467 |doi=10.1007/978-3-642-38896-5}}</ref><ref name=Wild>{{cite journal |first1=Paul |last1=Vitányi |author1-link=Paul Vitanyi |first2=Lambert |last2=Meertens |author2-link=Lambert Meertens |title=Big Omega versus the wild functions |journal=ACM SIGACT News |volume=16 |issue=4 |date=April 1985 |pages=56–59 |doi=10.1145/382242.382835 |url=http://www.kestrel.edu/home/people/meertens/publications/papers/Big_Omega_contra_the_wild_functions.pdf  |doi-access=free |s2cid-access=free |citeseerx=10.1.1.694.3072 |s2cid=11700420 |access-date=2017-03-14 |archive-date=2016-03-10 |archive-url=https://web.archive.org/web/20160310012405/http://www.kestrel.edu/home/people/meertens/publications/papers/Big_Omega_contra_the_wild_functions.pdf |url-status=live }}</ref><ref name="knuth"/><ref name="HL"/>
|-
| <math>f(n) = o(g(n))</math>
| Small O; Small Oh; Little O; Little Oh
| {{mvar|f}} is dominated by {{mvar|g}} asymptotically (for any constant factor <math>k</math>)
| <math>\forall k>0 \, \exists n_0 \, \forall n > n_0\colon  |f(n)| \leq k\, g(n)</math>
| <math>\lim_{n \to \infty} \frac{f(n)}{g(n)} = 0</math>
|-
| <math>f(n) = O(g(n))</math>
| Big O; Big Oh; Big Omicron
| <math>|f|</math> is asymptotically bounded above by {{mvar|g}} (up to constant factor <math>k</math>)
| <math>\exists k > 0 \, \exists n_0 \, \forall n>n_0\colon  |f(n)| \leq k\, g(n)</math>
| <math>\limsup_{n \to \infty} \frac{\left|f(n)\right|}{g(n)} < \infty</math>
|-
| <math>f(n) \asymp g(n)</math> (Hardy's notation) or <math>f(n) = \Theta(g(n))</math> (Knuth notation)
| Of the same order as (Hardy); Big Theta (Knuth)
| {{mvar|f}} is asymptotically bounded by {{mvar|g}} both above (with constant factor <math>k_2</math>) and below (with constant factor <math>k_1</math>)
| <math>\exists k_1 > 0 \, \exists k_2>0 \, \exists n_0 \, \forall n > n_0\colon</math>  <math>k_1 \, g(n) \leq f(n) \leq k_2 \, g(n)</math>
| <math>f(n) = O(g(n))</math> and <math>g(n) = O(f(n))</math>  
|-
| <math>f(n)\sim g(n)</math>
| Asymptotic equivalence
| {{mvar|f}} is equal to {{mvar|g}} [[Asymptotic analysis|asymptotically]]
| <math>\forall \varepsilon > 0 \, \exists n_0 \, \forall n > n_0\colon \left| \frac{f(n)}{g(n)} - 1 \right|  < \varepsilon</math>
| <math>\lim_{n \to \infty} \frac{f(n)}{g(n)} = 1</math>
|-
| <math>f(n) = \Omega(g(n))</math>
| Big Omega in complexity theory (Knuth)
| {{mvar|f}} is bounded below by {{mvar|g}} asymptotically
| <math>\exists k > 0 \, \exists n_0 \, \forall n>n_0\colon f(n) \geq k\, g(n)</math>
| <math>\liminf_{n \to \infty} \frac{f(n)}{g(n)} > 0 </math>
|-
| <math>f(n) = \omega(g(n))</math>
| Small Omega; Little Omega
| {{mvar|f}} dominates {{mvar|g}} asymptotically
| <math>\forall k > 0 \, \exists n_0 \, \forall n > n_0 \colon f(n) > k\, g(n)</math>
| <math>\lim_{n \to \infty} \frac{f(n)}{g(n)} = \infty</math>
|- #style="border-top: 2px solid gray;"
| <math>f(n) = \Omega(g(n))</math>
| Big Omega in number theory (Hardy–Littlewood)
| <math>|f|</math> is not dominated by {{mvar|g}} asymptotically
| <math>\exists k>0 \, \forall n_0 \, \exists n > n_0\colon |f(n)| \geq k\, g(n)</math>
| <math>\limsup_{n \to \infty} \frac{\left|f(n)\right|}{g(n)} > 0 </math>
|}

The limit definitions assume <math>g(n) > 0</math> for sufficiently large <math>n</math>. The table is (partly) sorted from smallest to largest, in the sense that <math>o,O,\Theta,\sim,   </math> (Knuth's version of) <math>\Omega, \omega   </math> on functions correspond to <math><,\leq,\approx,=,   </math><math>\geq,>   </math> on the real line<ref name=Wild/> (the Hardy–Littlewood version of <math>\Omega   </math>, however, doesn't correspond to any such description).

Computer science uses the big <math>O   </math>, big Theta <math>\Theta   </math>, little <math>o   </math>, little omega <math>\omega   </math> and Knuth's big Omega <math>\Omega   </math> notations.<ref>{{Introduction to Algorithms|edition=2|pages=41–50}}</ref> Analytic number theory often uses the big <math>O   </math>, small <math>o   </math>, Hardy's <math>\asymp</math>,<ref name=GT>Gérald Tenenbaum, Introduction to analytic and probabilistic number theory, « Notation », page xxiii. American Mathematical Society, Providence RI, 2015.</ref> Hardy–Littlewood's big Omega <math>\Omega   </math> (with or without the +, − or ± subscripts) and <math>\sim</math> notations.<ref name=Ivic/> The small omega <math>\omega   </math> notation is not used as often in analysis.<ref>for example it is omitted in: {{cite web |last1=Hildebrand |first1=A.J. |title=Asymptotic Notations |url=http://www.math.uiuc.edu/~ajh/595ama/ama-ch2.pdf |website=Asymptotic Methods in Analysis |series=Math&nbsp;595, Fall 2009 |publisher=University of Illinois |place=Urbana, IL |department=Department of Mathematics |access-date=14 March 2017 |archive-date=14 March 2017 |archive-url=https://web.archive.org/web/20170314153801/http://www.math.uiuc.edu/~ajh/595ama/ama-ch2.pdf |url-status=live }}</ref>