Vizualizare sursă pentru „Notația Big O”

[[Fișier:Big-O-notation.png|miniatura|300x300px| Exemplu de notație Big O: {{Color|#ff0000|{{math|''f''(''x'')}}}} ∈ O ({{Color|#0000ff|{{math|''g''(''x'')}}}}) deoarece există {{math|''c'' > 0}} (de exemplu, {{math|1=''c'' = 1}}) și {{math|''x''<sub>0</sub>}} (de exemplu, {{math|1=''x''<sub>0</sub> = 5}}) astfel încât {{Color|#ff0000|{{math|''f''(''x'')}}}} ≤ {{math|''c'' {{Color|#0000ff|''g''(''x'')}}}} pentru orice {{math|''x'' ≥ ''x''<sub>0</sub>}}. ]]
'''Notația Big O''' este o [[notație matematică]] care descrie {{Ill-wd|Q752718|3=comportamentul la limită}} al unei [[Funcție|funcții]] atunci când [[Argumentul unei funcții|argumentul]] tinde la o anumită valoare sau la infinit. Este una din notațiile inventate de [[Paul Bachmann]],<ref name="Bachmann">{{Citat carte|prenume=Paul|nume=Bachmann|legătură-autor=Paul Bachmann|titlu=Analytische Zahlentheorie|titlu_trad=Analytic Number Theory|limbă=de|volum=2|locul-publicării=Leipzig|editură=Teubner|dată=1894|url=https://archive.org/stream/dieanalytischeza00bachuoft#page/402/mode/2up}}</ref> {{Ill-wd|Q58750}},<ref name="Landau">{{Citat carte|prenume=Edmund|nume=Landau|legătură-autor=Edmund Landau|titlu=Handbuch der Lehre von der Verteilung der Primzahlen|editură=B. G. Teubner|dată=1909|locul-publicării=Leipzig|titlu_trad=Manual de teoria distribuției numerelor prime|limbă=de|pagină=883|url=https://archive.org/details/handbuchderlehre01landuoft}}</ref> și alții, numite colectiv '''notațiile Bachmann-Landau''' sau '''notațiile asimptotice'''. 

În [[informatică]], notația Big O este folosită pentru a [[Teoria complexității|clasifica algoritmii]] în funcție de felul în care timpul lor de rulare sau cerințele lor de spațiu cresc pe măsură ce crește dimensiunea datelor de intrare.<ref name="quantumcomplexity">{{Citat web|url=http://www.austinmohr.com/Work_files/complexity.pdf|nume=Mohr|accessdate=7 June 2014|first1=Austin|pagină=2|titlu=Quantum Computing in Complexity Theory and Theory of Computation|language=en}}</ref> În [[teoria analitică a numerelor]], notația Big O este adesea folosită pentru a exprima o legătură între diferența dintre o {{Ill-wd|Q140744|3=funcție aritmetică}} și o aproximare mai bine înțeleasă; un exemplu celebru de astfel de diferență este termenul rest din [[teorema numerelor prime]]. 

Notatia Big O caracterizează funcțiile după de vitezele lor de creștere: funcții diferite cu aceeași viteză de creștere pot fi reprezentate folosind aceeași notație O. 

Litera O este folosită deoarece viteza de creștere a unei funcții este numită și '''ordin al funcției'''. O descriere a unei funcții în ceea ce privește notația Big O, de obicei, oferă doar o {{Ill-wd|Q13222579|3=limită superioară}} a vitezei de creștere a funcției. Cu notația Big O mai sunt asociate mai multe alte notații, folosind simbolurile {{Math|''o'', Ω, ω,}} și {{math|Θ}}, pentru a descrie alte tipuri de limite ale vitezelor de creștere asimptotică. 

Notația Big O este folosită și în multe alte domenii pentru a furniza estimări similare.

== Definiție formală ==
Fie {{Math|''f''}} o funcție cu valori reale sau complexe și {{Math|''g''}} o funcție cu valori reale, ambele fiind definite pe unele submulțimi nemărginite ale mulțimii [[Număr real|numerelor reale pozitive]], astfel încât {{Math|''g(x)''}} să fie strict pozitivă pentru toate valorile suficient de mari ale lui {{Math|''x''}}.<ref name=LandauO>{{cite book |first=Edmund |last=Landau |authorlink=Edmund Landau |title=Handbuch der Lehre von der Verteilung der Primzahlen |publisher=B. G. Teubner |date=1909 |location=Leipzig |trans-title=Manual de teoria distribuției numerelor prime |language=de |page=31 | url=https://archive.org/stream/handbuchderlehre01landuoft#page/31/mode/2up}}</ref> Se scrie 

:<math>f(x)=O(g(x))\text{ când }x\to\infty</math>

[[Dacă și numai dacă|dacă și numai dacă]] pentru toate valorile suficient de mari ale lui {{Math|''x''}}, valoarea absolută a lui {{Math|''f(x)''}} este cel mult un [[multiplu]] constant pozitiv al lui {{Math|''g(x)''}}. Adică, {{Math|1=''f(x) = O(g(x))''}} dacă și numai dacă există un număr real pozitiv ''M'' și un număr real {{Math|''x<sub>0</sub>''}} astfel încât 

:<math>|f(x)| \le \; M g(x)\text{ pentru orice }x \ge x_0.</math>

În multe contexte, ipoteza că suntem interesați de viteza de creștere când variabila {{Math|''x''}} tinde la infinit este lăsată nestabilită, și se scrie mai simplu că 

:<math>f(x) = O(g(x)).</math>

Notația poate fi folosită și pentru a descrie comportamentul lui {{Math|''f''}}  în preajma unui număr real {{Math|''a''}} (adesea, {{Math|1=''a = 0''}}): se spune 

:<math>f(x)=O(g(x))\text{ când }x\to a</math>

dacă și numai dacă există numere pozitive {{math|δ}} și {{math|''M''}} astfel încât 


:<math>|f(x)| \le \; M g(x)\text{ când } 0 < |x - a| < \delta.</math>

Întrucât {{Math|''g''(''x'')}} este aleasă în așa fel încât să fie nenulă, pentru valori ale lui {{Math|''x''}} {{Ill-wd|Q728368|3=suficient de apropiate}} de {{Math|''a''}}'','' ambele aceste definiții pot fi unificate folosind {{Ill-wd|Q1076611|3=limita superioară}}: 


:<math>f(x)=O(g(x))\text{ când }x \to a</math>

dacă și numai dacă 


:<math>\limsup_{x\to a} \left|\frac{f(x)}{g(x)}\right| < \infty.</math>

== Exemplu ==
În uzul tipic, definiția oficială a notației ''O'' nu este folosită direct; mai degrabă, notația ''O'' pentru o funcție {{Math|''f''}} se deduce din următoarele reguli de simplificare: 

* Dacă {{Math|''f(x)''}} este o sumă de câțiva termeni, dacă există unul cu cea mai mare viteză de creștere, el poate fi păstrat și toți ceilalți omiși. 
* Dacă {{Math|''f(x)''}} este un produs al mai multor factori, orice constantă (termen din produs care nu depinde de {{Math|''x''}}) poate fi omisă. 

De exemplu, fie {{math|1=''f''(''x'') = 6''x''<sup>4</sup> - 2''x''<sup>3</sup> + 5}} și se presupune că se dorește simplificarea acestei funcții, folosind notația ''O'', pentru a descrie viteza de creștere a acesteia când {{Math|''x''}} tinde la infinit.  Această funcție este suma a trei termeni: {{math|6''x''<sup>4</sup>}}, {{math|-2''x''<sup>3</sup>}} și {{math|5}}. Din cei trei termeni, cel cu cea mai mare viteză de creștere este cel cu cel mai mare exponent în funcție de {{Math|''x''}}, și anume {{math|6''x''<sup>4</sup>}}. Acum se poate aplica a doua regulă: {{math|6''x''<sup>4</sup>}} este un produs de 6 și {{math|''x''<sup>4</sup>}} în care primul factor nu depinde de {{Math|''x''}}. Omiterea acestui factor are ca rezultat forma simplificată {{math|''x''<sup>4</sup>}}. Astfel, spunem că {{Math|''f''(''x'')}} este un „big-O” al lui ({{math|''x''<sup>4</sup>}}). Matematic, putem scrie {{math|1=''f''(''x'') = ''O''(''x''<sup>4</sup>)}}. Se poate confirma acest calcul folosind definiția formală: fie {{math|1=''f''(''x'') = 6''x''<sup>4</sup> - 2''x''<sup>3</sup> + 5}} și {{math|1=''g''(''x'') = ''x''<sup>4</sup>}}. Aplicând [[#Definiție formală|definiția formală]] de mai sus, afirmația că {{math|1=''f''(''x'') = ''O''(''x''<sup>4</sup>)}} este echivalentă cu dezvoltarea sa, 
:<math>|f(x)| \le \; M x^4</math>
pentru un {{Math|''x''<sub>0</sub>}} și un {{Math|''M''}} aleși adecvat și pentru orice {{Math|''x'' > ''x''<sub>0</sub>}}. Pentru a demonstra acest lucru, fie {{Math|1=''x''<sub>0</sub> = 1}} și {{Math|1=''M'' = 13}}. Atunci, pentru orice {{Math|''x'' > ''x''<sub>0</sub>}}: 
:<math>\begin{align}|6x^4 - 2x^3 + 5| &\le 6x^4 + |2x^3| + 5\\
                                      &\le 6x^4 + 2x^4 + 5x^4\\
                                      &= 13x^4\end{align}</math>
așa că
:<math> |6x^4 - 2x^3 + 5| \le 13 \,x^4 .</math>

== Utilizare ==
Notația Big O are două domenii principale de aplicare: 

* în [[matematică]] , este utilizată în mod obișnuit pentru a descrie [[#Asimptotica infinitezimală|cât de aproape este o serie finită aproximând o anumită funcție]], în special în cazul unei [[Serie Taylor|serii Taylor]] trunchiate sau al unei {{Ill-wd|Q752726|3=dezvoltări asimptotice}} 
* în [[Informatică|domeniul informaticii]], este utilă în [[#Asimptotica infinită|analiza algoritmilor]] 

În ambele aplicații, funcția {{Math|''g(x)''}} care apare în cadrul lui ''O'' (...) este de obicei aleasă așa încât să fie cât mai simplă posibil, omițând factori constanți și termeni de ordin inferior. 

Există două utilizări formale apropiate, dar cu totul diferite, ale acestei notații: 

* asimptotica [[Infinit|infinită]] 
* asimptotica [[Infinitezimal|infinitezimală]]. 

Distincția aceasta există doar în practică, nu și în principiu{{Mdash}} definiția formală pentru „big O” este aceeași pentru ambele cazuri, cu limite diferite pentru argumentul funcției. 

=== Asimptotica infinită ===
[[Fișier:Comparison_computational_complexity.svg|miniatura| Graficele funcțiilor utilizate în mod obișnuit în analiza algoritmilor, care arată numărul de operații {{Math|''N''}} în raport cu dimensiunea intrării {{Math|''n''}} pentru fiecare funcție ]]
Notația Big O este utilă atunci când se {{Ill-wd|Q333464|3=analizează eficiența algoritmilor}}. De exemplu, timpul (sau numărul de pași) necesar pentru a rezolva o problemă de dimensiune {{Math|''n''}} poate fi găsit a fi {{math|1=''T''(''n'') = 4''n''<sup>2</sup> - 2''n'' + 2}}. Când {{Math|''n''}} crește foarte mult, termenul {{Math|''n<sup>2</sup>''}} ajunge să domine, astfel încât toți ceilalți termeni pot fi neglijați, de exemplu, atunci când {{Math|1=''n'' = 500}}, termenul {{Math|4''n''<sup>2</sup>}} este de 1000 de ori mai mare ca termenul {{Math|2''n''}}. Ignorarea acestuia din urmă ar avea un efect neglijabil asupra valorii expresiei pentru cele mai multe scopuri. Mai mult, [[Coeficient|coeficienții]] devin irelevanți dacă comparăm cu oricare alt ordin al expresiei, cum ar fi o expresie care conține un termen {{Math|''n''<sup>3</sup>}} sau {{Math|''n''<sup>4</sup>}}''.'' Chiar dacă {{Math|1=''T(n)'' = 1.000.000 ''n''<sup>2</sup>}}, dacă {{Math|1=''U(n)'' = ''n''<sup>3</sup>}}, acesta din urmă îl va depăși întotdeauna pe primul când {{Math|''n''}}  crește mai mare decât 1.000.000 ({{Math|1=''T''(1.000.000) = 1.000.000<sup>3</sup> = ''U''(1.000.000)}}).  În plus, numărul de pași depinde de detaliile modelului mașinii pe care rulează algoritmul, dar diferite tipuri de mașini variază de obicei doar printr-un factor constant în numărul de pași necesari pentru executarea unui algoritm. Deci, notația Big O surprinde ceea ce rămâne: se scrie fie 
:<math>\ T(n)= O(n^2) </math>
fie 
:<math>T(n)\in O(n^2) </math>
și se spune că algoritmul are complexitate de ''ordinul lui'' {{Math|''n''<sup>2</sup>}}. Egalul nu mai reprezintă aici egalitate în sensul matematic normal, ci mai degrabă un „este“ mai popular, astfel încât a doua expresie este uneori considerată mai precisă (a se vedea discuția de mai jos despre [[semnul egal]]) în timp ce prima este considerată de unii ca un {{Ill-wd|Q842159|3=abuz de notație}}.<ref name="Introduction to Algorithms"/>

=== Asimptotica infinitezimală ===
Big O poate fi folosită și pentru a descrie [[Serie Taylor|termenul de eroare]] într-o aproximare a unei funcții matematice. Termenii cei mai semnificativi sunt scriși explicit, iar termenii cel mai puțin semnificativi sunt rezumați într-un singur termen Big O. Considerăm, de exemplu, {{Ill-wd|Q168698|3=seria exponențială}} și două expresii ale acesteia care sunt valabile atunci când {{Math|''x''}} este mic: 
:<math>\begin{align}
e^x &=1+x+\frac{x^2}{2!}+\frac{x^3}{3!}+\frac{x^4}{4!}+\dotsb &\text{oricare ar fi } x\\
    &=1+x+\frac{x^2}{2}+O(x^3)                             &\text{când } x\to 0\\
    &=1+x+O(x^2)                                           &\text{când } x\to 0\\
\end{align}</math>

Cea de a doua expresie (cea cu {{Math|''O''(''x''<sup>3</sup>)}}) înseamnă că valoarea absolută a erorii {{Math|e<sup>''x''</sup> - (1 + ''x''<sup>2</sup>/2)}} este de cel mult o constantă înmulțită cu {{Math|{{!}} ''x''<sup>3</sup> {{!}}}} când {{Math|''x''}} este suficient de aproape de 0.

== Proprietăți ==
Dacă funcția {{Math|''f''}} poate fi scrisă ca o sumă finită a altor funcții, atunci cea mai rapidă creștere determină ordinul lui {{Math|''f''(''n'')}}. De exemplu, 

:<math>f(n) = 9 \log n + 5 (\log n)^4 + 3n^2 + 2n^3 = O(n^3) \qquad\text{când } n\to\infty .</math>

În special, dacă o funcție poate fi legată de un polinom în {{Math|''n''}}, atunci când {{Math|''n''}} tinde spre ''infinit'', se pot ignora termenii de ''grad mai mic'' ai polinomului. De asemenea, mulțimile {{Math|''O''(''n''<sup>''c''</sup>)}} și {{Math|''O''(''c''<sup>''n''</sup>)}} sunt foarte diferiți. Dacă ''c'' este mai mare decât unu, atunci acesta crește mult mai repede. O funcție care crește mai repede decât {{Math|''n''<sup>''c''</sup>}} pentru oricare {{Math|''c''}} se numește ''superpolinomială''. Una care crește mai lent decât orice [[funcție exponențială]] de forma {{Math|''c''<sup>''n''</sup>}}  se numește ''subexponențială''. Un algoritm poate necesita timp atât superpolimonial cât și subexponențial; printre astfel de exemple se numără algoritmii cei mai rapizi cunoscuți pentru [[Factorizarea întregilor|factorizarea numerelor întregi]] și funcția {{Math|''n''<sup>log ''n''</sup>}}. 

Se poate ignora orice putere a lui {{Math|''n''}} din interiorul logaritmilor. Mulțimea {{Math|''O'' (log ''n'')}} este exact același cu {{Math|''O'' (log ''n''<sup>c</sup>)}}.  Logaritmii diferă numai printr-un factor constant (întrucât {{Math|1=log ''n''<sup>''c''</sup> = ''c'' log ''n''}}) și astfel notația Big O ignoră termenul. Similar, logaritmii cu diferite baze constante sunt echivalenți. Pe de altă parte, exponențialele cu baze diferite nu sunt de același ordin. De exemplu, {{Math|2<sup>''n''</sup>}} nu este același lucru cu {{Math|3<sup>''n''</sup>}}. 

Schimbarea unităților poate sau nu poate afecta ordinul algoritmului rezultat. Modificarea unităților este echivalentă cu înmulțirea variabilei corespunzătoare cu o constantă oriunde apare.  De exemplu, dacă un algoritm rulează în timp de ordinul lui {{Math|''n''<sup>2</sup>}}, înlocuirea {{Math|''n''}} cu {{Math|''cn''}} înseamnă că algoritmul rulează în timp de ordinul lui {{Math|''c''<sup>2</sup>''n''<sup>2</sup>}}, iar notația Big O ignoră constanta {{Math|''c''<sup>2</sup>}}. Aceasta se poate scrie ca {{Math|1=''c''<sup>2</sup>''n''<sup>2</sup> = ''O''(''n''<sup>2</sup>)}}.  Dacă, totuși, un algoritm rulează în timp de ordinul lui {{Math|2<sup>''n''</sup>}}, înlocuirea lui {{Math|''n''}} cu {{Math|''cn''}} dă timp de ordinul {{Math|1=2<sup>''cn''</sup> = (2<sup>''c''</sup>)<sup>''n''</sup>}}.  Aceasta nu este echivalentă cu {{Math|2<sup>''n''</sup>}} în general.  Schimbarea variabilelor poate afecta, de asemenea, ordinul algoritmului rezultat. De exemplu, dacă timpul de execuție al algoritmului este {{Math|''O''(''n'')}} atunci când este măsurat în termeni de număr {{Math|''n''}} de ''cifre'' al unui număr de intrare {{Math|''x''}}, timpul său de execuție este {{Math|''O''(log ''x'')}} ca funcție de numărul de intrare ''x'' însuși, deoarece {{Math|1=''n'' = ''O''(log ''x'')}}. 

=== Produsul ===
:<math> f_1 = O(g_1) \text{ and } f_2 = O(g_2)\, \Rightarrow f_1  f_2 = O(g_1  g_2)</math>
:<math>f\cdot O(g) = O(f g)</math>

=== Suma ===

:<math> f_1 = O(g_1) \text{ și }
  f_2= O(g_2)\, \Rightarrow f_1 + f_2 = O(max(g_1, g_2))</math>

Aceasta înseamnă că <math> f_1 = O(g) \text{ și } f_2 = O(g) \Rightarrow f_1+f_2 \in O(g) </math>, ceea ce înseamnă că <math>O(g)</math> este un con convex.

=== Înmulțirea cu o constantă ===

: Fie {{Math|''k''}} o constantă. Atunci: 
:<math>\ O(|k| g) = O(g)</math> dacă {{math|''k''}} este nenul.
:<math>f= O(g) \Rightarrow kf = O(g). </math>

== Mai multe variabile ==
Big ''O'' (și little o, Ω, etc.) pot fi utilizate și cu mai multe variabile. Pentru a defini Big ''O'' în mod formal pentru mai multe variabile, se presupune că {{Math|''f''}} și {{Math|''g''}} sunt două funcții definite pe o anumită submulțime a lui  <math>\mathbb{R}^n</math>. Se spune că 
:<math>f(\vec{x})\text{ este }O(g(\vec{x}))\text{ când }\vec{x}\to\infty</math>
dacă și numai dacă <ref>{{Citat carte|nume=Cormen|prenume=Thomas|nume2=Leiserson|prenume2=Charles|nume3=Rivest|prenume3=Ronald|nume4=Stein|prenume4=Clifford|titlu=Introduction to Algorithms|dată=2009|editură=MIT|pagină=53|ediție=Third|language=en|trans_title=Introducere în algoritmi}}</ref> 
:<math>\exists M\,\exists C>0\text{ astfel încât pentru orice }\vec{x} \text{ with } x_i \ge M \text{ pentru orice }i, |f(\vec{x})| \le C |g(\vec{x})|.</math>
În mod echivalent, condiția <math>x_i \geq M</math> pentru unii <math>i</math> poate fi înlocuită cu condiția <math>\|\vec{x}\|_{\infty} \ge M</math>, unde cu <math>\|\vec{x}\|_{\infty}</math> se notează {{Ill-wd|Q1202673|3=norma Cebîșev}}.  De exemplu, afirmația 
:<math>f(n,m) = n^2 + m^3 + O(n+m) \text{ când } n,m\to\infty</math>
spune că există constantele {{Math|''C''}} și {{Math|''M''}} astfel încât 
:<math>\forall \|(n, m)\|_{\infty} \geq M:  |g(n,m)| \le C|n+m|,</math>
unde {{Math|''g''(''n'', ''m'')}} se definește ca 
:<math>f(n,m) = n^2 + m^3 + g(n,m).</math>
Această definiție permite ca toate componentele lui <math>\vec{x}</math> să crească până la infinit. În special, afirmația 
:<math>f(n,m) = O(n^m) \text{ când } n,m\to\infty</math>
(de exemplu, <math>\exists C\,\exists M\,\forall n\,\forall m\dots</math>) este destul de diferită de 
:<math>\forall m\colon f(n,m) = O(n^m) \text{ când } n\to\infty</math>
(de exemplu, <math>\forall m\,\exists C\,\exists M\,\forall n\dots</math>). 

Sub această definiție, submulțimea pe care este definită o funcție este semnificativă atunci când se generalizează afirmațiile de la contextul univariabilă la cel multivariabilă. De exemplu, dacă <math>f(n,m)=1</math> și <math>g(n,m)=n</math>, atunci <math>f(n,m)=O(g(n,m))</math> dacă se restrâng {{math|''f''}} și {{math|''g''}} la <math>[1,\infty)^2</math>, dar nu dacă acestea sunt definite pe <math>[0,\infty)^2</math>. 

Aceasta nu este singura generalizare a notației ''Big O'' la funcții multivariabilă, dar în practică există o oarecare inconsistență în alegerea definiției.<ref>{{Citat web|url=http://people.cis.ksu.edu/~rhowell/asymptotic.pdf|nume=Howell|accessdate=2015-04-23|first1=Rodney|titlu=On Asymptotic Notation with Multiple Variables}}</ref>

== Chestiuni de notație ==

=== Semnul egal ===
Afirmația {{Math|''f''(''x'')}} este {{Math|''O''(''g''(''x''))}}, așa cum este definită mai sus, se scrie de obicei ca {{Math|1=''f''(''x'') = ''O''(''g''(''x''))}}.  Unii consideră că acest lucru este un {{Ill-wd|Q842159|3=abuz de notație}}, deoarece utilizarea semnului egal ar putea fi înșelătoare, deoarece sugerează o simetrie, pe care această afirmație nu o are. După cum spune {{Ill-wd|Q1078285|3=de Bruijn}}, este adevărat că {{Math|1=''O''(''x'') = ''O''(''x''<sup>2</sup>)}}, dar nu și că {{Math|1=''O''(''x''<sup>2</sup>) = ''O''(''x'')}}.<ref>{{Citat carte|nume={{Ill-wd|Q1078285}}|titlu=Asymptotic Methods in Analysis|locul-publicării=Amsterdam|editură=North-Holland|an=1958|pagini=5–7|url=https://books.google.com/books?id=_tnwmvHmVwMC&pg=PA5&vq=%22The+trouble+is%22|isbn=978-0-486-64221-5}}</ref> [[Donald E. Knuth|Knuth]] denumește astfel de afirmații „egalități unidirecționale”, deoarece dacă s-ar inversa cele două părți, „am putea deduce lucruri ridicole cum ar fi {{Math|1=''n'' = ''n''<sup>2</sup>}} din identitățile {{Math|1=''n'' = ''O''(''n''<sup>2</sup>)}}și {{Math|1=''n''<sup>2</sup> = ''O''(''n''<sup>2</sup>)}}.” <ref name="Concrete Mathematics">{{Citat carte|nume=Graham|prenume=Ronald|legătură-autor=Ronald Graham|prenume2=Donald|nume2=Knuth|legătură-autor2=Donald Knuth|nume3=Patashnik|prenume3=Oren|legătură-autor3=Oren Patashnik|titlu=Concrete Mathematics|locul-publicării=Reading, Massachusetts|editură=Addison–Wesley|ediție=2|dată=1994|pagină=446|url=https://books.google.com/books?id=pntQAAAAMAAJ|isbn=978-0-201-55802-9}}</ref> 

Din aceste motive, ar fi mai precis să folosim {{Ill-wd|Q7456286|3=notația mulțimilor}} și să scriem {{Math|''f''(''x'') ∈ ''O''(''g''(''x''))}}, considerând {{Math|''O''(''g''(''x''))}} ca clasă a tuturor funcțiilor {{Math|''h''(''x'')}} astfel încât {{Math|{{!}} ''h''(''x'') {{!}} ≤ ''C'' {{!}} ''g''(''x'') {{!}}}} pentru o constantă {{Math|''C''}}''.''<ref name="Concrete Mathematics"/> Cu toate acestea, utilizarea semnului egal este obișnuită. Knuth a subliniat că „matematicienii folosesc în mod obișnuit semnul = așa cum folosesc cuvântul «este» în limba engleză: [[Aristotel]] este un om, dar un om nu este neapărat Aristotel.”<ref>{{Citat revistă|nume=Donald Knuth|dată=June–July 1998|titlu=Teach Calculus with Big O|url=http://www.ams.org/notices/199806/commentary.pdf|journal={{Ill-wd|Q24158}}|volum=45|număr=6|pagină=687}} ([http://www-cs-staff.stanford.edu/~knuth/ocalc.tex Unabridged version] {{Webarchive|url=https://web.archive.org/web/20080513234708/http://www-cs-staff.stanford.edu/~knuth/ocalc.tex |date=2008-05-13 }})</ref> 

=== Alți operatori aritmetici ===
Notația Big O poate fi utilizată și în combinație cu alți operatori aritmetici în ecuații mai complicate. De exemplu, cu {{Math|''h''(''x'') + ''O''(''f''(''x''))}} se notează colecția de funcții având creșterea {{Math|''h''(''x'')}} plus o parte a cărei creștere este limitată la {{Math|''f''(''x'')}}. Prin urmare, 

:<math>g(x) = h(x) + O(f(x))</math>

exprimă același lucru ca și 

:<math>g(x) - h(x) = O(f(x))\,.</math>

==== Exemplu ====
Să presupunem că se dezvoltă un [[algoritm]] care să funcționeze pe o mulțime de {{Math|''n''}} elemente.  Dezvoltatorii săi sunt interesați să găsească o funcție {{Math|''T''(''n'')}} care să exprime cât timp va dura rularea algoritmului (în unele măsurători arbitrare ale timpului) în termeni de număr de elemente din mulțimea de intrare. Algoritmul funcționează apelând mai întâi o subrutină pentru sortarea elementelor din mulțime și efectuarea propriilor operații. Sortarea are o complexitate în timp cunoscută de {{Math|''O''(''n''<sup>2</sup>)}}, iar după executarea subrutinei algoritmul trebuie să mai ruleze încă {{Math|55''n''<sup>3</sup> + 2''n'' + 10}} pași înainte de a se termina. Astfel, complexitatea în timp a algoritmului poate fi exprimată ca {{Math|1=''T''(''n'') = 55 ''n''<sup>3</sup> + ''O''(''n''<sup>2</sup>).}} Aici termenii {{Math|2''n'' + 10}} sunt subsumați în cadrul lui {{Math|''O''(''n''<sup>2</sup>)}} cu creștere mai rapidă. Din nou, această utilizare ignoră o parte din semnificația formală a simbolului „=”, dar permite utilizarea notației Big O ca un substitut convenabil.

=== Utilizări multiple ===
În utilizarea mai complicată, ''O'' (...) poate să apară în diferite locuri într-o ecuație, chiar și de mai multe ori pe fiecare parte.  De exemplu, următoarele sunt valabile pentru <math>n\to\infty</math>:

:<math>(n+1)^2 = n^2 + O(n)</math>
:<math>(n+O(n^{1/2}))(n + O(\log n))^2 = n^3 + O(n^{5/2})</math>
:<math>n^{O(1)} = O(e^n).</math>

Semnificația acestor afirmații este următoarea: pentru ''orice'' funcție care satisface fiecare {{math|''O'' (...)}} din partea stângă, există ''câteva'' funcții care satisfac fiecare {{math|''O'' (...)}} din partea dreaptă, astfel încât substituind toate aceste funcții, ecuația face ca cele două părți să fie egale. De exemplu, a treia ecuație de mai sus înseamnă: „Pentru orice funcție {{Math|1=''f''(''n'') = ''O''(1)}}, există o funcție {{Math|1=''g''(''n'') = ''O''(e<sup>''n''</sup>)}} astfel încât {{Math|1=''n''<sup>''f''(''n'')</sup> = ''g''(''n'')}}.” În ceea ce privește „notația mulțimilor” de mai sus, înțelesul este că clasa de funcții reprezentată de partea stângă este o submulțime a clasei de funcții reprezentate de partea dreaptă. În această utilizare, „=” este un simbol formal care, spre deosebire de utilizarea obișnuită a lui „=”, nu este o {{Ill-wd|Q621461|3=relație simetrică}}.  Astfel, de exemplu, {{Math|1=''n''<sup>''O''(1)</sup> = ''O''(e<sup>''n''</sup>)}} nu implică și afirmația falsă {{Math|1=''O''(e<sup>''n''</sup>) = ''n''<sup>''O''(1)</sup>}} 

=== Scriere ===
''Big O'' constă doar dintr-un „O” majuscul. Spre deosebire de notațiile cu nume grecești Bachmann-Landau, nu are nevoie de un simbol special. Cu toate acestea, variantele caligrafice frecvent utilizate, cum ar fi <math>\mathcal{O}</math>, sunt disponibile în sistemele [[LaTeX]] și în sisteme de fonturi derivate.<ref>{{Citat web|url=https://texblog.org/2014/06/24/big-o-and-related-notations-in-latex/|nume=Tom|date=24 June 2014|lucrare=texblog|titlu=Big O and related notations in LaTeX|language=en}}</ref>

== Ordinul de mărime al unor funcții comune ==
Mai jos sunt enumerate clase de funcții care se întâlnesc frecvent când se analizează timpul de funcționare al unui algoritm.  În fiecare caz, {{Math|''c''}} este o constantă pozitivă și {{Math|''n''}} crește fără limitări.  Funcțiile cu o creștere mai lentă sunt în general enumerate mai întâi. 
{| class="wikitable"
!Notație
!Nume
!Exemple
|-
|<math>O(1)</math>
|[[Complexitate în timp|constantă]]
|Determinarea dacă un număr binar este par sau impar; Calculul lui <math>(-1)^n</math>; Utilizarea unei {{Ill-wd|Q690265|3=tabele de corespondență}} de dimensiuni constante
|-
|<math>O(\log \log n)</math>
|dublu logaritmică
|Numărul de comparații folosit pentru a găsi  un element folosind {{Ill-wd|Q1147856|3=căutarea prin interpolare}} într-un tabel sortat de valori uniform distribuite
|-
|<math>O(\log n)</math>
|[[Complexitate în timp|logaritmică]]
|Găsirea unui element într-un tablou sortat cu [[căutare binară]] sau cu un {{Ill-wd|Q223655|3=arbore}} de căutare echilibrat, precum și toate operațiile pe un {{Ill-wd|Q864032|3=heap binomial}}
|-
|<math>O((\log n)^c)</math><br /><br /><math>\scriptstyle c>1</math>
|[[Complexitate în timp|polilogaritmică]]
|Ordonarea lanțurilor de matrice poate fi rezolvată în timp polilogaritmic pe o [[RAM paralel|mașină cu acces aleator paralel]].
|-
|<math>O(n^c)</math><br /><br /><math>\scriptstyle 0<c<1</math>
|putere fracționară
|Căutarea într-un {{Ill-wd|Q309949|3=arbore k-d}}
|-
|<math>O(n)</math>
|[[Complexitate în timp|liniară]]
|Găsirea unui element într-o listă neordonată sau într-un tablou neordonat; adunarea a doi întregi pe {{Math|''n''}} biți prin [[Sumator (electronică)|sumatoare]] cu transport.
|-
|<math>O(n\log^* n)</math>
|n [[Logaritm iterat]] n
|Efectuarea de [[triangularea unui poligon |triangulări ale unui poligon]] simplu folosind algoritmul lui Seidel, sau algoritmul union–find. <math>\log^*(n) =
\begin{cases}
 0, & \text{if }n \leq 1 \\
 1 + \log^*(\log n), & \text{if }n>1
\end{cases}</math>
|-
|<math>O(n\log n)=O(\log n!)</math>
|[[Complexitate în timp|linearitmică]], logliniară, sau cvasiliniară
|Efecturea unei {{Ill-wd|Q623950|3=transformări Fourier rapide}}; Cea mai rapidă {{Ill-wd|Q2632949|3=sortare cu comparație}}; {{Ill-wd|Q474095}} and [[merge sort]]
|-
|<math>O(n^2)</math>
|[[Complexitate în timp|pătratică]]
|Înmulțirea a două numere cu {{Math|''n''}} cifre printr-un algoritm simplu; algoritmi de sortare simpli, cum ar fi {{Ill-wd|Q60864}}, {{Ill-wd|Q220831}} și {{Ill-wd|Q117241}}; limita (în cel mai rău caz) a unor algoritmi de regulă mai rapizi, ca [[quicksort]], {{Ill-wd|Q848955}}, și {{Ill-wd|Q863521}}
|-
|<math>O(n^c)</math>
|[[Complexitate în timp|polinomială]] sau algebrică
|Parsarea unor {{Ill-wd|Q1754022|3=gramatici cu arbori adjuncți}}; {{Ill-wd|Q1065144|3=cuplajul}} maxim pentru [[Graf bipartit|grafuri bipartite]]; găsirea [[Determinant (matematică)|determinantului]] prin {{Ill-wd|Q833089|3=descompunere LU}}
|-
|<math>L_n[\alpha,c] = e^{(c+o(1)) (\ln n)^\alpha (\ln \ln n)^{1-\alpha}}</math><br /><br /><math>\scriptstyle 0 < \alpha < 1</math>
|{{Ill-wd|Q15401695|3=Notația L}} sau[[Complexitate în timp|subexponențială]]
|Factorizarea unui număr folosind {{Ill-wd|Q1151850|3=ciurul pătratic}} sau {{Ill-wd|Q140770|3=ciurul algebric}}
|-
|<math>O(c^n)</math><br /><br /><math>\scriptstyle c>1</math>
|[[Complexitate în timp|exponențtială]]
|Găsirea soluției (exacte) a [[Problema comis-voiajorului|problemei comis-voiajorului]] folosind {{Ill-wd|Q380679|3=programare dinamică}}; aflarea dacă două afirmații logice sunt echivalente folosind {{Ill-wd|Q850362|3=căutarea cu forță brută}}
|-
|<math>O(n!)</math>
|[[Factorial|factorială]]
|Rezolvarea [[Problema comis-voiajorului|problemei comis-voiajorului]] prin căutarea cu forță brută; generarea tuturor permutațiilor nerestricționate ale unei {{Ill-wd|Q474715|3=mulțimi parțial ordonate}}; găsirea [[Determinant (matematică)|determinantului]] prin [[Teorema lui Laplace (algebră)|dezvoltare Laplace]]; enumerarea {{Ill-wd|Q816063|3=tuturor partițiilor unei mulțimi}}
|}
Afirmația <math>f(n)=O(n!)</math> este uneori relaxată la <math>f(n)=O\left(n^n\right)</math> pentru a obține formule mai simple pentru complexitatea asimptotică. Pentru orice {{math|''k'' > 0}} și {{math|''c'' > 0}}, <math>O(n^c(\log n)^k)</math> este o submulțime a lui <math>O(n^{c+\varepsilon })</math> pentru orice <math> \varepsilon >0</math>, deci poate fi considerat ca un polinom de grad mai mare.

== Notații asimptotice asociate ==
Big ''O'' este cea mai frecvent folosită notație asimptotică pentru compararea funcțiilor.  Împreună cu alte notații asociate, ea formează familia notațiilor Bachmann-Landau. 

=== Notația Little-o ===
Intuitiv, afirmația „{{Math|''f''(''x'')}} este {{Math|''o''(''g''(''x''))}}” (a se citi {{Math|''f''(''x'')}} este little-o de {{Math|''g''(''x'')}} înseamnă că {{Math|''g''(''x'')}} crește mult mai rapid decât {{Math|''f''(''x'')}}. Fie {{Math|''f''}} ca înainte o funcție cu valori reale sau complexe și {{Math|''g''}} o funcție cu valori reale, ambele fiind definite pe unele submulțimi nemărginite ale [[Număr real|numerelor reale pozitive]], astfel încât {{Math|''g''(''x'')}} să fie strict pozitivă pentru toate valorile suficient de mari ale lui {{Math|''x''}}''.'' Se scrie 
:<math>f(x)=o(g(x))\text{ as }x\to\infty</math>
dacă pentru orice constantă pozitivă {{Math|''ε''}} există o constantă {{Math|''N''}} astfel încât 
:<math>|f(x)|\leq\varepsilon g(x)\qquad\text{ for all }x\geq N~.</math><ref name="Landausmallo">{{Citat carte|prenume=Edmund|nume=Landau|legătură-autor=Edmund Landau|titlu=Handbuch der Lehre von der Verteilung der Primzahlen|editură=B. G. Teubner|dată=1909|locul-publicării=Leipzig|titlu_trad=Handbook on the theory of the distribution of the primes|limbă=de|pagină=61|url=https://archive.org/stream/handbuchderlehre01landuoft#page/61/mode/2up}}</ref> 
De exemplu, avem 
: <math>2x  = o(x^2) </math> și <math>1/x = o(1).</math>

Diferența dintre [[#Definiție formală|definiția]] anterioară pentru notația big-O și definiția aceasta a lui little-o este că, în timp ce prima trebuie să fie adevărată pentru ''cel puțin o'' constantă {{Math|''M''}}, aceasta din urmă trebuie să fie valabilă pentru ''orice'' constantă pozitivă {{Math|''ε''}} , oricât de mică ar fi.<ref name="Introduction to Algorithms">Thomas H. Cormen et al., 2001, [http://highered.mcgraw-hill.com/sites/0070131511/ Introduction to Algorithms, Second Edition]{{Necesită pagina}}</ref> În acest fel, notația little-o face o ''afirmație mai puternică'' decât notația big-O corespunzătoare: orice funcție care este little-o a lui {{Math|''g''}} este de asemenea big O al lui ''g'', dar nu orice funcție care este big-O al lui {{Math|''g''}} este și little-o de {{Math|''g''}}.  De exemplu, <math>2x^2 = O(x^2) </math> dar <math>2x^2 \neq o(x^2). </math>

Deoarece {{Math|''g''(''x'')}} este nenul, sau cel puțin devine nenul dincolo de un anumit punct, relația {{Math|''f''(''x'')&nbsp;{{=}}&nbsp;''o''(''g''(''x''))}} este echivalentă cu 

:<math>\lim_{x \to \infty}\frac{f(x)}{g(x)}=0</math> (și așa a definit, de fapt, Landau <ref name="Landausmallo"/> notația little-o). 

Little-o respectă o serie de operații aritmetice. De exemplu, 
: dacă {{Mvar|c}} este o constantă nenulă și <math>f = o(g)</math> atunci <math>c \cdot f = o(g)</math>, și 
: dacă <math>f = o(F)</math> și <math>g = o(G)</math> atunci <math> f \cdot g = o(F \cdot G).</math> 
De asemenea, ea satisface o relație de tranzitivitate: 
: dacă <math> f = o(g)</math> și <math> g = o(h)</math> atunci <math> f = o(h).</math>

=== Notația Big Omega ===
Există două definiții foarte răspândite și incompatibile ale afirmației 

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

unde {{Math|''a''}} este un număr real, ∞ sau -∞, unde {{Math|''f''}} și {{Math|''g''}} sunt funcții reale definite într-o vecinătate a lui {{Math|''a''}} și unde {{Math|''g''}} este pozitivă în această vecinătate. 

Prima (cronologic) este folosită în [[teoria analitică a numerelor]], iar cealaltă în [[teoria complexității]].  Când se întâlnesc cele două subiecte, această situație este generatoare de confuzie.

==== Definiția Hardy-Littlewood ====
În 1914, {{Ill-wd|Q184337}} și {{Ill-wd|Q353426}} au introdus noul simbol <math>\Omega</math>,<ref name="HL">{{Citat revistă|nume=Hardy|nume2=Littlewood|prenume=G. H.|prenume2=J. E.|dată=1914|titlu=Some problems of diophantine approximation: Part II. The trigonometrical series associated with the elliptic ϑ-functions|language=en|url=http://projecteuclid.org/download/pdf_1/euclid.acta/1485887376|journal=Acta Mathematica|volum=37|pagină=225|language=en|doi=10.1007/BF02401834}}</ref> care este definit după cum urmează: 

:<math>f(x)=\Omega(g(x))\ (x\rightarrow\infty)\;\Leftrightarrow\;\limsup_{x \to \infty} \left|\frac{f(x)}{g(x)}\right|> 0.</math>

Prin urmare <math>f(x)=\Omega(g(x))</math> este negarea lui <math>f(x)=o(g(x))</math>.

În 1916, aceiași autori au introdus cele două noi simboluri <math>\Omega_R</math> și <math>\Omega_L</math>, definite astfel:<ref name="HL2"> GH Hardy și JE Littlewood, „Contribution to the theory of the Riemann zeta-function and the theory of the distribution of primes”, ''[[Acta Mathematica]]'' , vol. 41, 1916. </ref> 

:<math>f(x)=\Omega_R(g(x))\ (x\rightarrow\infty)\;\Leftrightarrow\;\limsup_{x \to \infty} \frac{f(x)}{g(x)}> 0</math>;

:<math>f(x)=\Omega_L(g(x))\ (x\rightarrow\infty)\;\Leftrightarrow\;\liminf_{x \to \infty} \frac{f(x)}{g(x)}< 0. </math>

Aceste simboluri au fost folosite de {{Ill-wd|Q58750}}, cu aceleași semnificații, în 1924.<ref name="landau"> E. Landau, "De la Anzahl der Gitterpunkte in gewissen Bereichen." NAChR. Gesell. Wiss. Gott. Math-Phys. Kl. 1924, 137-150. </ref>  După Landau, notațiile nu au fost niciodată folosite din nou exact așa; <math>\Omega_R</math> a devenit <math>\Omega_+</math> și <math>\Omega_L</math> a devenit <math>\Omega_-</math>.

Aceste trei simboluri <math>\Omega, \Omega_+, \Omega_-</math>, precum și <math>f(x)=\Omega_\pm(g(x))</math> (ceea ce înseamnă că sunt satisfăcute ambele relații<math>f(x)=\Omega_+(g(x))</math> și <math>f(x)=\Omega_-(g(x))</math>), sunt acum utilizate în prezent în [[teoria analitică a numerelor]].<ref name="Ivic"> Aleksandar Ivić. The Riemann zeta-function, capitolul 9. John Wiley & Sons 1985. </ref> <ref> Gérald Tenenbaum, Introduction to analytic and probabilistic number theory, capitolul I.5. [[American Mathematical Society]], Providence RI, 2015. </ref> 

===== Exemple simple =====
Avem 

:<math>\sin x=\Omega(1)\ (x\rightarrow\infty),</math>

și mai precis 

:<math>\sin x=\Omega_\pm(1)\ (x\rightarrow\infty).</math>

Avem 

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

și mai precis 

:<math>\sin x+1=\Omega_+(1)\ (x\rightarrow\infty);</math>

dar 

:<math>\sin x+1\not=\Omega_-(1)\ (x\rightarrow\infty).</math>

==== Definiția Knuth ====
În 1976, [[Donald E. Knuth|Donald Knuth]] a publicat o lucrare pentru a justifica utilizarea simbolului <math>\Omega</math> pentru a descrie o proprietate mai puternică. Knuth a scris: „Pentru toate aplicațiile pe care le-am văzut până acum în domeniul informaticii, o cerință mai puternică [...] este mult mai potrivită”. El a definit 

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

cu comentariul: „Deși am schimbat definiția dată de Hardy și a Littlewood pentru <math>\Omega</math>, mă simt justificat în acest sens, deoarece definiția lor nu este deloc folosită pe scară largă și pentru că există și alte modalități de a spune ceea ce vor ei să spună în cazurile relativ rare în care se aplică definiția lor.”<ref name="knuth">Donald Knuth. " [http://www.phil.uu.nl/datastructuren/10-11/knuth_big_omicron.pdf Big Omicron and big Omega and big Theta] {{Webarchive|url=https://web.archive.org/web/20211130005215/https://www.phil.uu.nl/datastructuren/10-11/knuth_big_omicron.pdf |date=2021-11-30 }} ", SIGACT News, aprilie-iunie 1976, 18-24.</ref>

=== Familia de notații Bachmann-Landau ===
{| class="wikitable"
!Notația
!Nume<ref name="knuth"/>
!Descriere
!Definiție formală
!Limit Definition<ref name="Balcázar">{{Citat revistă|nume=Balcázar|nume2=Gabarró|prenume=José L.|prenume2=Joaquim|titlu=Nonuniform complexity classes specified by lower and upper bounds|url=http://archive.numdam.org/article/ITA_1989__23_2_177_0.pdf|journal=RAIRO – Theoretical Informatics and Applications – Informatique Théorique et Applications|volum=23|număr=2|pagină=180|language=en|issn=0988-3754|access-date=14 March 2017}}</ref><ref name="Cucker">{{Citat carte|nume=Cucker|prenume=Felipe|nume2=Bürgisser|prenume2=Peter|titlu=Condition: The Geometry of Numerical Algorithms|dată=2013|editură=Springer|locul-publicării=Berlin, Heidelberg|isbn=978-3-642-38896-5|pagini=467–468|capitol=A.1  Big Oh, Little Oh, and Other Comparisons|doi=10.1007/978-3-642-38896-5}}</ref><ref name="Wild">{{Citat revistă|nume=Vitányi|nume2=Meertens|prenume=Paul|prenume2=Lambert|legătură-autor=Paul Vitanyi|legătură-autor2=Lambert Meertens|dată=April 1985|titlu=Big Omega versus the wild functions|language=en|url=http://www.kestrel.edu/home/people/meertens/publications/papers/Big_Omega_contra_the_wild_functions.pdf|journal=ACM SIGACT News|volum=16|număr=4|pagini=56–59|doi=10.1145/382242.382835}}</ref><ref name="knuth" /><ref name="HL"/>
|-
|<math>f(n) = o(g(n))</math>
|Small O; Small Oh
|{{Mvar|f}} este dominată de {{Mvar|g}} asimptotic
|<math>\forall k>0 \; \exists n_0 \; \forall n>n_0 \; |f(n)| < k\cdot 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> este mărginită superior de {{Mvar|g}} (până la un factor constant) asimptotic
|<math>\exists k>0 \; \exists n_0 \; \forall n>n_0 \; |f(n)| \leq k\cdot g(n)</math>
|<math>\limsup_{n \to \infty} \frac{\left|f(n)\right|}{g(n)} < \infty</math>
|-
|<math>f(n) = \Theta(g(n))</math>
|Big Theta
|{{Mvar|f}} este mărginită atât superior cât și inferior de {{Mvar|g}} asimptotic
|<math>\exists k_1>0 \; \exists k_2>0 \; \exists n_0 \; \forall n>n_0</math><math>k_1\cdot g(n) \leq f(n) \leq k_2\cdot g(n)</math>
|<math>f(n) = O(g(n))</math> și <math>f(n) = \Omega(g(n))</math> (versiunea Knuth)
|-
|<math>f(n)\sim g(n)</math>
|De ordinul lui
|{{Mvar|f}} este egal cu {{Mvar|g}} asimptotic
|<math>\forall \varepsilon>0\;\exists n_0\;\forall n>n_0\;\left|{f(n) \over g(n)}-1\right|<\varepsilon</math>
|<math>\lim_{n \to \infty} {f(n) \over g(n)} = 1</math>
|-
|<math>f(n) = \Omega(g(n))</math>
|Big Omega în teoria numerelor (Hardy–Littlewood)
|<math>|f|</math> nu este dominată de {{Mvar|g}} asimptotic
|<math>\exists k>0 \; \forall n_0 \; \exists n>n_0 \; |f(n)| \geq k\cdot g(n)</math>
|<math>\limsup_{n \to \infty} \left|\frac{f(n)}{g(n)}\right| > 0 </math>
|-
|<math>f(n) = \Omega(g(n))</math>
|Big Omega în teoria complexității (Knuth)
|{{Mvar|f}} este mărginit inferior de {{Mvar|g}} asimptotic
|<math>\exists k>0 \; \exists n_0 \; \forall n>n_0 \; f(n) \geq k\cdot g(n)</math>
|<math>\liminf_{n \to \infty} \frac{f(n)}{g(n)} > 0 </math>
|-
|<math>f(n) = \omega(g(n))</math>
|Small Omega
|{{Mvar|f}} domină {{Mvar|g}} asimptotic
|<math>\forall k>0 \; \exists n_0 \; \forall n>n_0 \  |f(n)| > k\cdot |g(n)|</math>
|<math>\lim_{n \to \infty} \left|\frac{f(n)}{g(n)}\right| = \infty</math>
|}
Definițiile limitelor presupun <math>g(n) \neq 0</math> pentru {{Mvar|n}} suficient de mare. Tabelul este (parțial) sortat de la cel mai mic la cel mai mare, în sensul că o, O, Θ, ~, Ω (versiunea lui Knuth), ω pe funcții corespund cu <, ≤, ≈, =, ≥, > pe [[dreapta reală]]<ref name="Wild"/> (versiunea Hardy-Littlewood a lui Ω nu corespunde însă unei astfel de descrieri). 

Informatica folosește Big ''O'', big Theta Θ, little ''o'', omega &omega; și notația Big Omega Ω a lui Knuth.<ref>{{Introduction to Algorithms|edition=2|pages=41–50}}</ref>  Teoria analitică a numerelor utilizează adesea big ''O'', small ''o'', Big Omega Ω a lui Hardy-Littlewood (cu sau fără indicele +, - sau ±) și notațiile <math>\sim</math>.<ref name="Ivic"/> Notația small omega ω nu este utilizată la fel de des în analiză.<ref>de exemplu, este omisă în: {{Citat web|url=http://www.math.uiuc.edu/~ajh/595ama/ama-ch2.pdf|nume=Hildebrand|accessdate=14 March 2017|publisher=Math 595, Fall 2009|first1=A.J.|lucrare=Asymptotic Methods in Analysis|titlu=Asymptotic Notations|language=en}}</ref>

=== Utilizarea în informatică ===
În mod informal, în special în domeniul informaticii, notația big ''O'' poate fi folosită oarecum diferit pentru a descrie o legătură asimptotică strânsă acolo unde notația Theta Θ ar putea fi mai potrivită într-un anumit context. De exemplu, atunci când se analizează o funcție {{Math|1=''T''(''n'') = 73''n''<sup>3</sup> + 22''n''<sup>2</sup> + 58}}, toate afirmațiile următoare sunt în general acceptabile, dar limite mai stricte (cum ar fi numerele 2 și 3 de mai jos) sunt de obicei preferate în locul limitelor mai relaxate (cum ar fi numărul 1 de mai jos). 

# {{Math|1=''T''(''n'') = ''O''(''n''<sup>100</sup>)}} 
# {{Math|1=''T''(''n'') = ''O''(''n''<sup>3</sup>)}} 
# {{Math|1=''T''(''n'') = Θ(''n''<sup>3</sup>)}} 

Afirmațiile echivalente în română sunt: 

# {{Math|''T''(''n'')}} crește asymptotic nu mai repede decât {{Math|''n''<sup>100</sup>}} 
# {{Math|''T''(''n'')}} crește asymptotic nu mai repede decât {{Math|''n''<sup>3</sup>}} 
# {{Math|''T''(''n'')}} crește asimptotic la fel de repede ca {{Math|''n''<sup>3</sup>}}. 

Deci, în timp ce toate cele trei afirmații sunt adevărate, în fiecare din ele există progresiv mai multe informații. În unele domenii, cu toate acestea, notația Big O (numărul 2 din listele de mai sus) ar fi folosită mai frecvent decât notația Big Theta (punctele 3 din listele de mai sus). De exemplu, dacă {{Math|''T''(''n'')}} reprezintă timpul de funcționare a algoritmului nou dezvoltat pentru dimensiunea de intrare {{Math|''n''}}, inventatorii și utilizatorii algoritmului ar putea fi mai înclinați să pună o limită asimptotică superioară timpului cât va dura funcționarea lui, fără a face vreo afirmație explicită despre limita inferioară asimptotică.

=== Alte notații ===
În cartea lor ''{{Ill-wd|Q1141518|3=Introducere în algoritmi}}'', {{Ill-wd|Q2524992|3=Cormen}}, {{Ill-wd|Q93028|3=Leiserson}}, [[Ronald Rivest|Rivest]] și {{Ill-wd|Q2024396|3=Stein}} iau în considerare mulțimea funcțiilor {{Math|''f''}} care satisfac 

:<math> f(n) = O(g(n))\  (n\rightarrow\infty).</math>

Într-o notație corectă, această mulțime poate fi, de exemplu, numită {{Math|''O''(''g'')}}, unde 

:<math>O(g) = \{ f :</math> există constante pozitive {{Math|''c''}} și <math>n_0</math> astfel încât <math>0 \le f(n) \le cg(n)</math> pentru toți <math>n \ge n_0 \}</math>.<ref>{{Citat carte|isbn=978-0-262-53305-8|nume=Thomas H. Cormen|nume2=Charles E. Leiserson|nume3=Ronald L. Rivest|titlu=Introduction to Algorithms|locul-publicării=Cambridge/MA|editură=MIT Press|ediție=3rd|an=2009|pagină=47|language=en|citat=When we have only an asymptotic upper bound, we use O-notation. For a given function ''g''(''n''), we denote by ''O''(''g''(''n'')) (pronounced “big-oh of ''g'' of ''n''” or sometimes just “oh of ''g'' of ''n''”) the set of functions ''O''(''g''(''n'')) = { ''f''(''n'') : there exist positive constants ''c'' and ''n''<sub>0</sub> such that 0 ≤ ''f''(''n'') ≤ ''cg''(''n'') for all ''n'' ≥ ''n''<sub>0</sub><nowiki>}</nowiki>}}</ref> 

Autorii afirmă că folosirea operatorului de egalitate (=) pentru a nota apartenența la mulțime, în locul operatorului de apartenență încetățenit (∈), este un abuz de notație, dar acest lucru are avantaje.<ref name="clrs3">{{Citat carte|isbn=978-0-262-53305-8|nume=Thomas H. Cormen|nume2=Charles E. Leiserson|nume3=Ronald L. Rivest|titlu=Introduction to Algorithms|locul-publicării=Cambridge/MA|editură=MIT Press|ediție=3rd|an=2009|pagină=45|citat=Because ''θ''(''g''(''n'')) is a set, we could write "''f''(''n'') ∈ ''θ''(''g''(''n''))" to indicate that ''f''(''n'') is a member of ''θ''(''g''(''n'')). Instead, we will usually write ''f''(''n'') = ''θ''(''g''(''n'')) to express the same notion. You might be confused because we abuse equality in this way, but we shall see later in this section that doing so has its advantages.}}</ref>  Într-o ecuație sau inegalitate, folosirea unei notații asimptotice reprezintă o funcție anonimă din mulțimea {{Math|''O''(''g'')}}, care elimină termenii de ordin inferior și ajută la reducerea aglomerării inutile în ecuații, de exemplu: <ref>{{Citat carte|isbn=978-0-262-53305-8|nume=Thomas H. Cormen|language=en|nume2=Charles E. Leiserson|nume3=Ronald L. Rivest|titlu=Introduction to Algorithms|locul-publicării=Cambridge/MA|editură=MIT Press|ediție=3rd|an=2009|pagină=49|citat=When the asymptotic notation stands alone (that is, not within a larger formula) on the right-hand side of an equation (or inequality), as in n = O(n²), we have already defined the equal sign to mean set membership: n ∈ O(n²). In general, however, when asymptotic notation appears in a formula, we interpret it as standing for some anonymous function that we do not care to name. For example, the formula 2''n''<sup>2</sup> + 3''n'' + 1 = 2''n''<sup>2</sup> + ''θ''(''n'') means that 2''n''<sup>2</sup> + 3''n'' + 1 = 2''n''<sup>2</sup> + ''f''(''n''), where ''f''(''n'') is some function in the set ''θ''(''n''). In this case, we let ''f''(''n'') = 3''n'' + 1, which is indeed in ''θ''(''n''). Using asymptotic notation in this manner can help eliminate inessential detail and clutter in an equation.}}</ref> 

:<math> 2n^2 + 3n + 1=2n^2 + O(n).</math>

=== Extensii la notațiile Bachmann-Landau ===
O altă notație folosită uneori în domeniul informaticii este Õ (citiți ''soft-O''): {{Math|1=''f''(''n'') = ''Õ''(''g''(''n''))}} este o prescurtare pentru {{Math|1=''f''(''n'') = ''O''(''g''(''n'') log ''k'' ''g''(''n''))}} pentru un anume {{Math|''k''}}. În esență, este o notație Big O, ignorând factorii logaritmici, deoarece efectele ratei de creștere a unei alte funcții superlogaritmice indică o explozie a ratei de creștere pentru parametrii de intrare de dimensiuni mari, care este mai importantă pentru a prezice relele performanțe efectele mai fine cu care contribuie de factorul (factorii) de creștere logaritmică. Această notație este adesea folosită pentru a evita „pierderea în amănunte” în cadrul vitezelor de creștere care sunt declarate ca fiind prea strâns mărginite pentru chestiunea relevantă  (întrucât {{Math|log<sup>''k''</sup> ''n''}} este întotdeauna {{Math|''o''(''n''<sup>ε</sup>)}} pentru orice constantă {{Math|''k''}} și orice {{Math|ε > 0}}). 

De asemenea, {{Ill-wd|Q15401695|3=notația L}}, definită ca 
:<math>L_n[\alpha,c]=e^{(c+o(1))(\ln n)^\alpha(\ln\ln n)^{1-\alpha}}</math>
este convenabilă pentru funcțiile care sunt între [[Complexitate în timp#Timp polinomial|polinomială]] și [[Complexitate în timp#Timp exponențial|exponențială]] în raport cu <math>\ln n</math>.

== Generalizări și utilizări conexe ==
Generalizarea funcțiilor care iau valori în orice [[spațiu vectorial normat]] este simplă (înlocuind valoarea absolută cu norma), unde {{Math|''f''}} și {{Math|''g''}} nu este nevoie săi aibă valori în același spațiu. O generalizare a funcțiilor {{Math|''g''}} cu valori în orice {{Ill-wd|Q1046291|3=grup topologic}} este de asemenea posibilă. „Procesul de limitare” {{Math|''x''→''x''<sub>0</sub>}} poate fi și el generalizat prin introducerea unei {{Ill-wd|Q1052692|3=baze de filtrare}} arbitrare, adică a {{Ill-wd|Q1191147|3=rețelelor}} direcționate {{Math|''f''}} și {{Math|''g''}}. Notația {{Math|''o''}} poate fi folosită pentru a defini [[Derivată|derivate]] și [[Funcție derivabilă|diferențiabilitatea]] în spații destul de generale, precum și echivalența (asimptotică) a funcțiilor, 
:<math> f\sim g \iff (f-g) \in o(g) </math>
care este o [[relație de echivalență]] și o noțiune mai restrictivă decât relația „{{Math|''f''}} este {{Math|Θ(''g'')}}” de mai sus. (Se reduce la {{Math|1=lim ''f''/''g'' = 1}} dacă {{Math|''f''}} și {{Math|''g''}} sunt funcții cu valoare reală pozitivă.) De exemplu, {{Math|2''x''}} este {{Math|Θ(''x'')}}, dar {{Math|2''x'' - ''x''}} nu este {{Math|''o''(''x'')}}.

== Istorie (notații Bachmann-Landau, Hardy și Vinogradov) ==
Simbolul O a fost introdus pentru prima dată de teoreticianul numerelor [[Paul Bachmann]] în 1894, în al doilea volum al cărții sale {{Lang|de|Analytische Zahlentheorie}} („[[Teoria analitică a numerelor]]”), al cărei prim volum (care nu conținea încă notația Big O) a fost publicat în 1892.<ref name="Bachmann"/> Teoreticianul numerelor  {{Ill-wd|Q58750}} a adoptat-o și, astfel, a fost inspirat să introducă în 1909 notația o; <ref name="Landau"/> aici ambele sunt numite acum simboluri Landau. Aceste notații au fost folosite în matematica aplicată în anii 1950 pentru analiza asimptotică.<ref>{{Citat carte|titlu=Asymptotic Expansions|nume=Erdelyi|prenume=A.|an=1956|isbn=978-0-486-60318-6}}</ref> Simbolul <math>\Omega</math> (în sensul „nu este {{Math|''o''}} de”) a fost introdus în 1914 de Hardy și Littlewood.<ref name="HL"/> Hardy și Littlewood au introdus, de asemenea, în 1918 simbolurile <math>\Omega_R</math> („dreapta”) și <math>\Omega_L</math> („stânga”), <ref name="HL2"/> precursori ai simbolurilor moderne <math>\Omega_+</math> („nu este mai mică decât small {{Math|''o''}} de”) și <math>\Omega_-</math> („nu este mai mare decât small {{Math|''o''}} de”).  Astfel, simbolurile Omega (cu semnificațiile lor originale) sunt uneori denumite și „simboluri Landau”. Această notație <math>\Omega</math> a devenit frecvent folosită în [[teoria numerelor]] cel puțin din anii 1950.<ref name="titchmarsh"> EC Titchmarsh, The Theory of the Riemann Zeta-Function (Oxford, Clarendon Press, 1951) </ref>  În anii 1970, Big O a fost popularizată în domeniul informaticii de către [[Donald E. Knuth|Donald Knuth]], care a introdus notația aferentă Theta și a propus o altă definiție pentru notația Omega.<ref name="knuth"/>

Landau nu a folosit niciodată Theta mare și simboluri omega-mic. 

Simbolurile lui Hardy erau (din punct de vedere al notației ''O'' moderne) 

:<math> f \preccurlyeq g\iff f \in O(g) </math> &nbsp; and &nbsp; <math> f\prec g\iff f\in o(g); </math>

(Hardy însă nu a definit niciodată și nu a folosit notația <math>\prec\!\!\prec</math>, nici <math>\ll</math>, așa cum s-a afirmat uneori). De asemenea, Hardy a introdus simbolurile <math>\preccurlyeq </math> și <math>\prec </math> (precum și alte simboluri) în tratatul său din 1910, „Orders of Infinity”, și îl folosește doar în trei lucrări (1910-1913). În restul de aproape 400 de lucrări și cărți, el folosește consistent simbolurile Landau O și o. 

Notația lui Hardy nu mai este folosită. Pe de altă parte, în 1930,<ref>Vezi de exemplu „O nouă estimare pentru ''G''(''n'') în problema lui Waring” (în rusă). Doklady Akademii Nauk SSSR 5, No 5-6 (1934), 249–253. Traducere în engleză în: Selected works / Ivan Matveevič Vinogradov ; îngrijită de Institutul Matematic Steklov al Academiei de Științe a URSS cu ocazia sărbătoririi a 90 de ani de la nașterea lui. Springer-Verlag, 1985.</ref> teoreticianului rus al numerelor {{Ill-wd|Q451330|3=Ivan Matveievici Vinogradov}} a introdus notația lui, <math>\ll</math>, care este folosită din ce în ce mai mult în teoria numerelor în locul notației <math>O</math>. Avem 
:<math> f\ll g \iff f \in O(g), </math>
și în mod obișnuit ambele notații sunt utilizate în aceeași lucrare. 

Big O reprezenta inițial „de ordinul lui” ("Ordnung", Bachmann 1894) și este așadar o literă latină.  Nici Bachmann, nici Landau nu o numesc vreodată „Omicron”.  Simbolul a fost considerat mult mai târziu (1976) de către Knuth drept [[omicron]] mare<ref name="knuth"/> probabil în legătură cu definiția sa a simbolului [[Omega (literă)|Omega]]. Nu se folosește cifra [[0 (cifră)|zero]].

== Note ==
<references/>

== Lectură suplimentară ==

* {{Citat carte|prenume=G. H.|nume=Hardy|legătură-autor=G. H. Hardy|titlu=Orders of Infinity: The 'Infinitärcalcül' of Paul du Bois-Reymond|dată=1910|url=https://archive.org/details/ordersofinfinity00harduoft|editură=[[Cambridge University Press]]}} 
* {{Citat carte|prenume=Donald|nume=Knuth|legătură-autor=Donald Knuth|titlu=Fundamental Algorithms|volum=1|serie=The Art of Computer Programming|ediție=3rd|editură=Addison–Wesley|dată=1997|isbn=978-0-201-89683-1|capitol=1.2.11: Asymptotic Representations}} 
* {{Citat carte|prenume=Thomas H.|nume=Cormen|legătură-autor=Thomas H. Cormen|prenume2=Charles E.|nume2=Leiserson|legătură-autor2=Charles E. Leiserson|prenume3=Ronald L.|nume3=Rivest|legătură-autor3=Ronald L. Rivest|prenume4=Clifford|nume4=Stein|legătură-autor4=Clifford Stein|titlu=Introduction to Algorithms|ediție=2nd|editură=MIT Press and McGraw–Hill|dată=2001|isbn=978-0-262-03293-3|capitol=3.1: Asymptotic notation}} 
* {{Citat carte|prenume=Michael|nume=Sipser|legătură-autor=Michael Sipser|an=1997|titlu=Introduction to the Theory of Computation|editură=PWS Publishing|isbn=978-0-534-94728-6|pagini=226–228}} 
* {{Cite conference|last=Avigad|last2=Donnelly|given=Jeremy|first2=Kevin|date=2004|conference=International Joint Conference on Automated Reasoning|title=Formalizing O notation in Isabelle/HOL|url=http://www.andrew.cmu.edu/~avigad/Papers/bigo.pdf|format=PDF|doi=10.1007/978-3-540-25984-8_27}} 
* {{Citat web|url=https://xlinux.nist.gov/dads/HTML/bigOnotation.html|nume=Black|accessdate=16 decembrie 2006|publisher=U.S. National Institute of Standards and Technology|date=11 March 2005|first1=Paul E.|editor-last=Black|editor-first=Paul E.|lucrare=Dictionary of Algorithms and Data Structures|titlu=big-O notation}} 
* {{Citat web|url=https://xlinux.nist.gov/dads/HTML/littleOnotation.html|nume=Black|accessdate=16 decembrie 2006|publisher=U.S. National Institute of Standards and Technology|date=17 December 2004|first1=Paul E.|editor-last=Black|editor-first=Paul E.|lucrare=Dictionary of Algorithms and Data Structures|titlu=little-o notation}} 
* {{Citat web|url=https://xlinux.nist.gov/dads/HTML/omegaCapital.html|nume=Black|accessdate=16 decembrie 2006|publisher=U.S. National Institute of Standards and Technology|date=17 December 2004|first1=Paul E.|editor-last=Black|editor-first=Paul E.|lucrare=Dictionary of Algorithms and Data Structures|titlu=Ω}} 
* {{Citat web|url=https://xlinux.nist.gov/dads/HTML/omega.html|nume=Black|accessdate=16 decembrie 2006|publisher=U.S. National Institute of Standards and Technology|date=17 December 2004|first1=Paul E.|editor-last=Black|editor-first=Paul E.|lucrare=Dictionary of Algorithms and Data Structures|titlu=ω}} 
* {{Citat web|url=https://xlinux.nist.gov/dads/HTML/theta.html|nume=Black|accessdate=16 decembrie 2006|publisher=U.S. National Institute of Standards and Technology|date=17 December 2004|first1=Paul E.|editor-last=Black|editor-first=Paul E.|lucrare=Dictionary of Algorithms and Data Structures|titlu=Θ}}

== Legături externe ==

* [[oeis:wiki/Growth_of_sequences|Creșterea șirurilor - OEIS (Online Encyclopedia of Integer Sequences) Wiki]] 
* [https://classes.soe.ucsc.edu/classes/cmps102/Spring04/TantaloAsymp.pdf Introducere în notații asimptotice]{{Legătură nefuncțională|date=decembrie 2022 |bot=InternetArchiveBot |fix-attempted=yes }} 
* [http://mathworld.wolfram.com/LandauSymbols.html Simboluri Landau] 
* [http://www.perlmonks.org/?node_id=573138 Notația Big-O - la ce servește] 
* [https://stackoverflow.com/questions/487258/what-is-a-plain-english-explanation-of-big-o-notation/50288253#50288253 Big O Notation explicată în engleză simplă] 
[[Categorie:Algoritmi]]