Notația Big O

Exemplu de notație Big O: f(x) ∈ O (g(x)) deoarece există c>0 (de exemplu, c=1) și x₀ (de exemplu, x₀=5) astfel încât f(x) ≤ c g(x) pentru orice x ≥ x₀.

Notația Big O este o notație matematică care descrie comportamentul la limită al unei funcții atunci când argumentul tinde la o anumită valoare sau la infinit. Este una din notațiile inventate de Paul Bachmann, Edmund Landau, și alții, numite colectiv notațiile Bachmann-Landau sau notațiile asimptotice.

În informatică, notația Big O este folosită pentru a 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. În teoria analitică a numerelor, notația Big O este adesea folosită pentru a exprima o legătură între diferența dintre o 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 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 o, Ω, ω, și Θ , 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 f o funcție cu valori reale sau complexe și g o funcție cu valori reale, ambele fiind definite pe unele submulțimi nemărginite ale mulțimii numerelor reale pozitive, astfel încât g(x) să fie strict pozitivă pentru toate valorile suficient de mari ale lui x. Se scrie

Nu s-a putut interpreta (eroare de sintaxă): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mi> <math>f(x)=O(g(x))\text{ as }x\to\infty} </mi><mo stretchy="false"> $f(x)=O(g(x)){\text{ as }}x\to \infty$ </mo><mi> $f(x)=O(g(x)){\text{ as }}x\to \infty$ </mi><mo stretchy="false"> $f(x)=O(g(x)){\text{ as }}x\to \infty$ </mo><mo> $f(x)=O(g(x)){\text{ as }}x\to \infty$ </mo><mi> $f(x)=O(g(x)){\text{ as }}x\to \infty$ </mi><mo stretchy="false"> $f(x)=O(g(x)){\text{ as }}x\to \infty$ </mo><mi> $f(x)=O(g(x)){\text{ as }}x\to \infty$ </mi><mo stretchy="false"> $f(x)=O(g(x)){\text{ as }}x\to \infty$ </mo><mi> $f(x)=O(g(x)){\text{ as }}x\to \infty$ </mi><mo stretchy="false"> $f(x)=O(g(x)){\text{ as }}x\to \infty$ </mo><mo stretchy="false"> $f(x)=O(g(x)){\text{ as }}x\to \infty$ </mo><mrow class="MJX-TeXAtom-ORD"><mtext> $f(x)=O(g(x)){\text{ as }}x\to \infty$ </mtext></mrow><mi> $f(x)=O(g(x)){\text{ as }}x\to \infty$ </mi><mo stretchy="false"> $f(x)=O(g(x)){\text{ as }}x\to \infty$ </mo><mi mathvariant="normal"> $f(x)=O(g(x)){\text{ as }}x\to \infty$ </mi></mstyle></mrow> </math>$f(x)=O(g(x)){\text{ as }}x\to \infty$ $f(x)=O(g(x)){\text{ as }}x\to \infty$ </img>

dacă și numai dacă pentru toate valorile suficient de mari ale lui x, valoarea absolută a lui f(x) este cel mult un multiplu constant pozitiv al lui g(x). Adică, f(x) = O(g(x)) dacă și numai dacă există un număr real pozitiv M și un număr real x₀ astfel încât

<mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mrow class="MJX-TeXAtom-ORD"><mo stretchy="false"> $|f(x)|\leq \;Mg(x){\text{ for all }}x\geq x_{0}.$ </mo></mrow><mi> $|f(x)|\leq \;Mg(x){\text{ for all }}x\geq x_{0}.$ </mi><mo stretchy="false"> $|f(x)|\leq \;Mg(x){\text{ for all }}x\geq x_{0}.$ </mo><mi> $|f(x)|\leq \;Mg(x){\text{ for all }}x\geq x_{0}.$ </mi><mo stretchy="false"> $|f(x)|\leq \;Mg(x){\text{ for all }}x\geq x_{0}.$ </mo><mrow class="MJX-TeXAtom-ORD"><mo stretchy="false"> $|f(x)|\leq \;Mg(x){\text{ for all }}x\geq x_{0}.$ </mo></mrow><mo> $|f(x)|\leq \;Mg(x){\text{ for all }}x\geq x_{0}.$ </mo><mi> $|f(x)|\leq \;Mg(x){\text{ for all }}x\geq x_{0}.$ </mi><mi> $|f(x)|\leq \;Mg(x){\text{ for all }}x\geq x_{0}.$ </mi><mo stretchy="false"> $|f(x)|\leq \;Mg(x){\text{ for all }}x\geq x_{0}.$ </mo><mi> $|f(x)|\leq \;Mg(x){\text{ for all }}x\geq x_{0}.$ </mi><mo stretchy="false"> $|f(x)|\leq \;Mg(x){\text{ for all }}x\geq x_{0}.$ </mo><mrow class="MJX-TeXAtom-ORD"><mtext> $|f(x)|\leq \;Mg(x){\text{ for all }}x\geq x_{0}.$ </mtext></mrow><mi> $|f(x)|\leq \;Mg(x){\text{ for all }}x\geq x_{0}.$ </mi><mo> $|f(x)|\leq \;Mg(x){\text{ for all }}x\geq x_{0}.$ </mo><msub><mi> $|f(x)|\leq \;Mg(x){\text{ for all }}x\geq x_{0}.$ </mi><mrow class="MJX-TeXAtom-ORD"><mn> $|f(x)|\leq \;Mg(x){\text{ for all }}x\geq x_{0}.$ </mn></mrow></msub><mo> $|f(x)|\leq \;Mg(x){\text{ for all }}x\geq x_{0}.$ </mo></mstyle></mrow> $|f(x)|\leq \;Mg(x){\text{ for all }}x\geq x_{0}.$ ${\displaystyle }$$|f(x)|\leq \;Mg(x){\text{ for all }}x\geq x_{0}.$ $|f(x)|\leq \;Mg(x){\text{ for all }}x\geq x_{0}.$ </img>

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

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

Nu s-a putut interpreta (eroare de sintaxă): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mi> <math>f(x)=O(g(x))\text{ as }x\to a} </mi><mo stretchy="false"> $f(x)=O(g(x)){\text{ as }}x\to a$ </mo><mi> $f(x)=O(g(x)){\text{ as }}x\to a$ </mi><mo stretchy="false"> $f(x)=O(g(x)){\text{ as }}x\to a$ </mo><mo> $f(x)=O(g(x)){\text{ as }}x\to a$ </mo><mi> $f(x)=O(g(x)){\text{ as }}x\to a$ </mi><mo stretchy="false"> $f(x)=O(g(x)){\text{ as }}x\to a$ </mo><mi> $f(x)=O(g(x)){\text{ as }}x\to a$ </mi><mo stretchy="false"> $f(x)=O(g(x)){\text{ as }}x\to a$ </mo><mi> $f(x)=O(g(x)){\text{ as }}x\to a$ </mi><mo stretchy="false"> $f(x)=O(g(x)){\text{ as }}x\to a$ </mo><mo stretchy="false"> $f(x)=O(g(x)){\text{ as }}x\to a$ </mo><mrow class="MJX-TeXAtom-ORD"><mtext> $f(x)=O(g(x)){\text{ as }}x\to a$ </mtext></mrow><mi> $f(x)=O(g(x)){\text{ as }}x\to a$ </mi><mo stretchy="false"> $f(x)=O(g(x)){\text{ as }}x\to a$ </mo><mi> $f(x)=O(g(x)){\text{ as }}x\to a$ </mi></mstyle></mrow> </math>$f(x)=O(g(x)){\text{ as }}x\to a$ $f(x)=O(g(x)){\text{ as }}x\to a$ </img>

dacă și numai dacă există numere pozitive δ și M astfel încât

<mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mrow class="MJX-TeXAtom-ORD"><mo stretchy="false"> $|f(x)|\leq \;Mg(x){\text{ when }}0<|x-a|<\delta .$ </mo></mrow><mi> $|f(x)|\leq \;Mg(x){\text{ when }}0<|x-a|<\delta .$ </mi><mo stretchy="false"> $|f(x)|\leq \;Mg(x){\text{ when }}0<|x-a|<\delta .$ </mo><mi> $|f(x)|\leq \;Mg(x){\text{ when }}0<|x-a|<\delta .$ </mi><mo stretchy="false"> $|f(x)|\leq \;Mg(x){\text{ when }}0<|x-a|<\delta .$ </mo><mrow class="MJX-TeXAtom-ORD"><mo stretchy="false"> $|f(x)|\leq \;Mg(x){\text{ when }}0<|x-a|<\delta .$ </mo></mrow><mo> $|f(x)|\leq \;Mg(x){\text{ when }}0<|x-a|<\delta .$ </mo><mi> $|f(x)|\leq \;Mg(x){\text{ when }}0<|x-a|<\delta .$ </mi><mi> $|f(x)|\leq \;Mg(x){\text{ when }}0<|x-a|<\delta .$ </mi><mo stretchy="false"> $|f(x)|\leq \;Mg(x){\text{ when }}0<|x-a|<\delta .$ </mo><mi> $|f(x)|\leq \;Mg(x){\text{ when }}0<|x-a|<\delta .$ </mi><mo stretchy="false"> $|f(x)|\leq \;Mg(x){\text{ when }}0<|x-a|<\delta .$ </mo><mrow class="MJX-TeXAtom-ORD"><mtext> $|f(x)|\leq \;Mg(x){\text{ when }}0<|x-a|<\delta .$ </mtext></mrow><mn> $|f(x)|\leq \;Mg(x){\text{ when }}0<|x-a|<\delta .$ </mn><mo> $|f(x)|\leq \;Mg(x){\text{ when }}0<|x-a|<\delta .$ </mo><mrow class="MJX-TeXAtom-ORD"><mo stretchy="false"> $|f(x)|\leq \;Mg(x){\text{ when }}0<|x-a|<\delta .$ </mo></mrow><mi> $|f(x)|\leq \;Mg(x){\text{ when }}0<|x-a|<\delta .$ </mi><mo> $|f(x)|\leq \;Mg(x){\text{ when }}0<|x-a|<\delta .$ </mo><mi> $|f(x)|\leq \;Mg(x){\text{ when }}0<|x-a|<\delta .$ </mi><mrow class="MJX-TeXAtom-ORD"><mo stretchy="false"> $|f(x)|\leq \;Mg(x){\text{ when }}0<|x-a|<\delta .$ </mo></mrow><mo> $|f(x)|\leq \;Mg(x){\text{ when }}0<|x-a|<\delta .$ </mo><mi> $|f(x)|\leq \;Mg(x){\text{ when }}0<|x-a|<\delta .$ </mi><mo> $|f(x)|\leq \;Mg(x){\text{ when }}0<|x-a|<\delta .$ </mo></mstyle></mrow> $|f(x)|\leq \;Mg(x){\text{ when }}0<|x-a|<\delta .$ ${\displaystyle }$$|f(x)|\leq \;Mg(x){\text{ when }}0<|x-a|<\delta .$ $|f(x)|\leq \;Mg(x){\text{ when }}0<|x-a|<\delta .$ </img>

Întrucât g(x) este aleasă în așa fel încât să fie nenulă, pentru valori ale lui x suficient de apropiate de a, ambele aceste definiții pot fi unificate folosind limita superioară:

Nu s-a putut interpreta (eroare de sintaxă): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mi> <math>f(x)=O(g(x))\text{ as }x \to a} </mi><mo stretchy="false"> $f(x)=O(g(x)){\text{ as }}x\to a$ </mo><mi> $f(x)=O(g(x)){\text{ as }}x\to a$ </mi><mo stretchy="false"> $f(x)=O(g(x)){\text{ as }}x\to a$ </mo><mo> $f(x)=O(g(x)){\text{ as }}x\to a$ </mo><mi> $f(x)=O(g(x)){\text{ as }}x\to a$ </mi><mo stretchy="false"> $f(x)=O(g(x)){\text{ as }}x\to a$ </mo><mi> $f(x)=O(g(x)){\text{ as }}x\to a$ </mi><mo stretchy="false"> $f(x)=O(g(x)){\text{ as }}x\to a$ </mo><mi> $f(x)=O(g(x)){\text{ as }}x\to a$ </mi><mo stretchy="false"> $f(x)=O(g(x)){\text{ as }}x\to a$ </mo><mo stretchy="false"> $f(x)=O(g(x)){\text{ as }}x\to a$ </mo><mrow class="MJX-TeXAtom-ORD"><mtext> $f(x)=O(g(x)){\text{ as }}x\to a$ </mtext></mrow><mi> $f(x)=O(g(x)){\text{ as }}x\to a$ </mi><mo stretchy="false"> $f(x)=O(g(x)){\text{ as }}x\to a$ </mo><mi> $f(x)=O(g(x)){\text{ as }}x\to a$ </mi></mstyle></mrow> </math>$f(x)=O(g(x)){\text{ as }}x\to a$ $f(x)=O(g(x)){\text{ as }}x\to a$ </img>

dacă și numai dacă

<mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><munder><mo movablelimits="true"> $\limsup _{x\to a}\left|{\frac {f(x)}{g(x)}}\right|<\infty .$ </mo><mrow class="MJX-TeXAtom-ORD"><mi> $\limsup _{x\to a}\left|{\frac {f(x)}{g(x)}}\right|<\infty .$ </mi><mo stretchy="false"> $\limsup _{x\to a}\left|{\frac {f(x)}{g(x)}}\right|<\infty .$ </mo><mi> $\limsup _{x\to a}\left|{\frac {f(x)}{g(x)}}\right|<\infty .$ </mi></mrow></munder><mrow><mo> $\limsup _{x\to a}\left|{\frac {f(x)}{g(x)}}\right|<\infty .$ </mo><mrow class="MJX-TeXAtom-ORD"><mfrac><mrow><mi> $\limsup _{x\to a}\left|{\frac {f(x)}{g(x)}}\right|<\infty .$ </mi><mo stretchy="false"> $\limsup _{x\to a}\left|{\frac {f(x)}{g(x)}}\right|<\infty .$ </mo><mi> $\limsup _{x\to a}\left|{\frac {f(x)}{g(x)}}\right|<\infty .$ </mi><mo stretchy="false"> $\limsup _{x\to a}\left|{\frac {f(x)}{g(x)}}\right|<\infty .$ </mo></mrow><mrow><mi> $\limsup _{x\to a}\left|{\frac {f(x)}{g(x)}}\right|<\infty .$ </mi><mo stretchy="false"> $\limsup _{x\to a}\left|{\frac {f(x)}{g(x)}}\right|<\infty .$ </mo><mi> $\limsup _{x\to a}\left|{\frac {f(x)}{g(x)}}\right|<\infty .$ </mi><mo stretchy="false"> $\limsup _{x\to a}\left|{\frac {f(x)}{g(x)}}\right|<\infty .$ </mo></mrow></mfrac></mrow><mo> $\limsup _{x\to a}\left|{\frac {f(x)}{g(x)}}\right|<\infty .$ </mo></mrow><mo> $\limsup _{x\to a}\left|{\frac {f(x)}{g(x)}}\right|<\infty .$ </mo><mi mathvariant="normal"> $\limsup _{x\to a}\left|{\frac {f(x)}{g(x)}}\right|<\infty .$ </mi><mo> $\limsup _{x\to a}\left|{\frac {f(x)}{g(x)}}\right|<\infty .$ </mo></mstyle></mrow> $\limsup _{x\to a}\left|{\frac {f(x)}{g(x)}}\right|<\infty .$ ${\displaystyle }$$\limsup _{x\to a}\left|{\frac {f(x)}{g(x)}}\right|<\infty .$ $\limsup _{x\to a}\left|{\frac {f(x)}{g(x)}}\right|<\infty .$ </img>

Exemplu

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

• Dacă 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ă f(x) este un produs al mai multor factori, orice constantă (termen din produs care nu depinde de x) poate fi omisă.

De exemplu, fie f ( x ) = 6 x ⁴   -   2 x ³   +   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 x tinde la infinit. Această funcție este suma a trei termeni: 6x⁴ , -2x³ și 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 x, și anume 6x⁴. Acum se poate aplica a doua regulă: 6 x ⁴ este un produs de 6 și x⁴ în care primul factor nu depinde de x. Omiterea acestui factor are ca rezultat forma simplificată x⁴. Astfel, spunem că f(x) este un „big-O” al lui (x⁴). Matematic, putem scrie f ( x )   =   O ( x ⁴ ). Se poate confirma acest calcul folosind definiția formală: fie f ( x )   =   6 x ⁴   -   2 x ³   +   5 și g ( x )   =   x ⁴ . Aplicând definiția formală de mai sus, afirmația că f ( x )   =   O ( x ⁴ ) este echivalentă cu expansiunea sa,

Nu s-a putut interpreta (eroare de sintaxă): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mrow class="MJX-TeXAtom-ORD"><mo stretchy="false"> <math>|f(x)| \le \; M x^4} </mo></mrow><mi> $|f(x)|\leq \;Mx^{4}$ </mi><mo stretchy="false"> $|f(x)|\leq \;Mx^{4}$ </mo><mi> $|f(x)|\leq \;Mx^{4}$ </mi><mo stretchy="false"> $|f(x)|\leq \;Mx^{4}$ </mo><mrow class="MJX-TeXAtom-ORD"><mo stretchy="false"> $|f(x)|\leq \;Mx^{4}$ </mo></mrow><mo> $|f(x)|\leq \;Mx^{4}$ </mo><mi> $|f(x)|\leq \;Mx^{4}$ </mi><msup><mi> $|f(x)|\leq \;Mx^{4}$ </mi><mrow class="MJX-TeXAtom-ORD"><mn> $|f(x)|\leq \;Mx^{4}$ </mn></mrow></msup></mstyle></mrow> </math>$|f(x)|\leq \;Mx^{4}$ $|f(x)|\leq \;Mx^{4}$ </img>

pentru un x₀ și un M aleși adecvat și pentru orice x > x₀ . Pentru a demonstra acest lucru, fie x₀ = 1 și M = 13. Atunci pentru orice x > x₀:

Nu s-a putut interpreta (eroare de sintaxă): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mrow class="MJX-TeXAtom-ORD"><mtable displaystyle="true" rowspacing="3pt"><mtr><mtd><mrow class="MJX-TeXAtom-ORD"><mo stretchy="false"> <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}} </mo></mrow><mn> ${\begin{aligned}|6x^{4}-2x^{3}+5|&\leq 6x^{4}+|2x^{3}|+5\\&\leq 6x^{4}+2x^{4}+5x^{4}\\&=13x^{4}\end{aligned}}$ </mn><msup><mi> ${\begin{aligned}|6x^{4}-2x^{3}+5|&\leq 6x^{4}+|2x^{3}|+5\\&\leq 6x^{4}+2x^{4}+5x^{4}\\&=13x^{4}\end{aligned}}$ </mi><mrow class="MJX-TeXAtom-ORD"><mn> ${\begin{aligned}|6x^{4}-2x^{3}+5|&\leq 6x^{4}+|2x^{3}|+5\\&\leq 6x^{4}+2x^{4}+5x^{4}\\&=13x^{4}\end{aligned}}$ </mn></mrow></msup><mo> ${\begin{aligned}|6x^{4}-2x^{3}+5|&\leq 6x^{4}+|2x^{3}|+5\\&\leq 6x^{4}+2x^{4}+5x^{4}\\&=13x^{4}\end{aligned}}$ </mo><mn> ${\begin{aligned}|6x^{4}-2x^{3}+5|&\leq 6x^{4}+|2x^{3}|+5\\&\leq 6x^{4}+2x^{4}+5x^{4}\\&=13x^{4}\end{aligned}}$ </mn><msup><mi> ${\begin{aligned}|6x^{4}-2x^{3}+5|&\leq 6x^{4}+|2x^{3}|+5\\&\leq 6x^{4}+2x^{4}+5x^{4}\\&=13x^{4}\end{aligned}}$ </mi><mrow class="MJX-TeXAtom-ORD"><mn> ${\begin{aligned}|6x^{4}-2x^{3}+5|&\leq 6x^{4}+|2x^{3}|+5\\&\leq 6x^{4}+2x^{4}+5x^{4}\\&=13x^{4}\end{aligned}}$ </mn></mrow></msup><mo> ${\begin{aligned}|6x^{4}-2x^{3}+5|&\leq 6x^{4}+|2x^{3}|+5\\&\leq 6x^{4}+2x^{4}+5x^{4}\\&=13x^{4}\end{aligned}}$ </mo><mn> ${\begin{aligned}|6x^{4}-2x^{3}+5|&\leq 6x^{4}+|2x^{3}|+5\\&\leq 6x^{4}+2x^{4}+5x^{4}\\&=13x^{4}\end{aligned}}$ </mn><mrow class="MJX-TeXAtom-ORD"><mo stretchy="false"> ${\begin{aligned}|6x^{4}-2x^{3}+5|&\leq 6x^{4}+|2x^{3}|+5\\&\leq 6x^{4}+2x^{4}+5x^{4}\\&=13x^{4}\end{aligned}}$ </mo></mrow></mtd><mtd><mo> ${\begin{aligned}|6x^{4}-2x^{3}+5|&\leq 6x^{4}+|2x^{3}|+5\\&\leq 6x^{4}+2x^{4}+5x^{4}\\&=13x^{4}\end{aligned}}$ </mo><mn> ${\begin{aligned}|6x^{4}-2x^{3}+5|&\leq 6x^{4}+|2x^{3}|+5\\&\leq 6x^{4}+2x^{4}+5x^{4}\\&=13x^{4}\end{aligned}}$ </mn><msup><mi> ${\begin{aligned}|6x^{4}-2x^{3}+5|&\leq 6x^{4}+|2x^{3}|+5\\&\leq 6x^{4}+2x^{4}+5x^{4}\\&=13x^{4}\end{aligned}}$ </mi><mrow class="MJX-TeXAtom-ORD"><mn> ${\begin{aligned}|6x^{4}-2x^{3}+5|&\leq 6x^{4}+|2x^{3}|+5\\&\leq 6x^{4}+2x^{4}+5x^{4}\\&=13x^{4}\end{aligned}}$ </mn></mrow></msup><mo> ${\begin{aligned}|6x^{4}-2x^{3}+5|&\leq 6x^{4}+|2x^{3}|+5\\&\leq 6x^{4}+2x^{4}+5x^{4}\\&=13x^{4}\end{aligned}}$ </mo><mrow class="MJX-TeXAtom-ORD"><mo stretchy="false"> ${\begin{aligned}|6x^{4}-2x^{3}+5|&\leq 6x^{4}+|2x^{3}|+5\\&\leq 6x^{4}+2x^{4}+5x^{4}\\&=13x^{4}\end{aligned}}$ </mo></mrow><mn> ${\begin{aligned}|6x^{4}-2x^{3}+5|&\leq 6x^{4}+|2x^{3}|+5\\&\leq 6x^{4}+2x^{4}+5x^{4}\\&=13x^{4}\end{aligned}}$ </mn><msup><mi> ${\begin{aligned}|6x^{4}-2x^{3}+5|&\leq 6x^{4}+|2x^{3}|+5\\&\leq 6x^{4}+2x^{4}+5x^{4}\\&=13x^{4}\end{aligned}}$ </mi><mrow class="MJX-TeXAtom-ORD"><mn> ${\begin{aligned}|6x^{4}-2x^{3}+5|&\leq 6x^{4}+|2x^{3}|+5\\&\leq 6x^{4}+2x^{4}+5x^{4}\\&=13x^{4}\end{aligned}}$ </mn></mrow></msup><mrow class="MJX-TeXAtom-ORD"><mo stretchy="false"> ${\begin{aligned}|6x^{4}-2x^{3}+5|&\leq 6x^{4}+|2x^{3}|+5\\&\leq 6x^{4}+2x^{4}+5x^{4}\\&=13x^{4}\end{aligned}}$ </mo></mrow><mo> ${\begin{aligned}|6x^{4}-2x^{3}+5|&\leq 6x^{4}+|2x^{3}|+5\\&\leq 6x^{4}+2x^{4}+5x^{4}\\&=13x^{4}\end{aligned}}$ </mo><mn> ${\begin{aligned}|6x^{4}-2x^{3}+5|&\leq 6x^{4}+|2x^{3}|+5\\&\leq 6x^{4}+2x^{4}+5x^{4}\\&=13x^{4}\end{aligned}}$ </mn></mtd></mtr><mtr><mtd><mo> ${\begin{aligned}|6x^{4}-2x^{3}+5|&\leq 6x^{4}+|2x^{3}|+5\\&\leq 6x^{4}+2x^{4}+5x^{4}\\&=13x^{4}\end{aligned}}$ </mo><mn> ${\begin{aligned}|6x^{4}-2x^{3}+5|&\leq 6x^{4}+|2x^{3}|+5\\&\leq 6x^{4}+2x^{4}+5x^{4}\\&=13x^{4}\end{aligned}}$ </mn><msup><mi> ${\begin{aligned}|6x^{4}-2x^{3}+5|&\leq 6x^{4}+|2x^{3}|+5\\&\leq 6x^{4}+2x^{4}+5x^{4}\\&=13x^{4}\end{aligned}}$ </mi><mrow class="MJX-TeXAtom-ORD"><mn> ${\begin{aligned}|6x^{4}-2x^{3}+5|&\leq 6x^{4}+|2x^{3}|+5\\&\leq 6x^{4}+2x^{4}+5x^{4}\\&=13x^{4}\end{aligned}}$ </mn></mrow></msup><mo> ${\begin{aligned}|6x^{4}-2x^{3}+5|&\leq 6x^{4}+|2x^{3}|+5\\&\leq 6x^{4}+2x^{4}+5x^{4}\\&=13x^{4}\end{aligned}}$ </mo><mn> ${\begin{aligned}|6x^{4}-2x^{3}+5|&\leq 6x^{4}+|2x^{3}|+5\\&\leq 6x^{4}+2x^{4}+5x^{4}\\&=13x^{4}\end{aligned}}$ </mn><msup><mi> ${\begin{aligned}|6x^{4}-2x^{3}+5|&\leq 6x^{4}+|2x^{3}|+5\\&\leq 6x^{4}+2x^{4}+5x^{4}\\&=13x^{4}\end{aligned}}$ </mi><mrow class="MJX-TeXAtom-ORD"><mn> ${\begin{aligned}|6x^{4}-2x^{3}+5|&\leq 6x^{4}+|2x^{3}|+5\\&\leq 6x^{4}+2x^{4}+5x^{4}\\&=13x^{4}\end{aligned}}$ </mn></mrow></msup><mo> ${\begin{aligned}|6x^{4}-2x^{3}+5|&\leq 6x^{4}+|2x^{3}|+5\\&\leq 6x^{4}+2x^{4}+5x^{4}\\&=13x^{4}\end{aligned}}$ </mo><mn> ${\begin{aligned}|6x^{4}-2x^{3}+5|&\leq 6x^{4}+|2x^{3}|+5\\&\leq 6x^{4}+2x^{4}+5x^{4}\\&=13x^{4}\end{aligned}}$ </mn><msup><mi> ${\begin{aligned}|6x^{4}-2x^{3}+5|&\leq 6x^{4}+|2x^{3}|+5\\&\leq 6x^{4}+2x^{4}+5x^{4}\\&=13x^{4}\end{aligned}}$ </mi><mrow class="MJX-TeXAtom-ORD"><mn> ${\begin{aligned}|6x^{4}-2x^{3}+5|&\leq 6x^{4}+|2x^{3}|+5\\&\leq 6x^{4}+2x^{4}+5x^{4}\\&=13x^{4}\end{aligned}}$ </mn></mrow></msup></mtd></mtr><mtr><mtd><mo> ${\begin{aligned}|6x^{4}-2x^{3}+5|&\leq 6x^{4}+|2x^{3}|+5\\&\leq 6x^{4}+2x^{4}+5x^{4}\\&=13x^{4}\end{aligned}}$ </mo><mn> ${\begin{aligned}|6x^{4}-2x^{3}+5|&\leq 6x^{4}+|2x^{3}|+5\\&\leq 6x^{4}+2x^{4}+5x^{4}\\&=13x^{4}\end{aligned}}$ </mn><msup><mi> ${\begin{aligned}|6x^{4}-2x^{3}+5|&\leq 6x^{4}+|2x^{3}|+5\\&\leq 6x^{4}+2x^{4}+5x^{4}\\&=13x^{4}\end{aligned}}$ </mi><mrow class="MJX-TeXAtom-ORD"><mn> ${\begin{aligned}|6x^{4}-2x^{3}+5|&\leq 6x^{4}+|2x^{3}|+5\\&\leq 6x^{4}+2x^{4}+5x^{4}\\&=13x^{4}\end{aligned}}$ </mn></mrow></msup></mtd></mtr></mtable></mrow></mstyle></mrow> </math>${\begin{aligned}|6x^{4}-2x^{3}+5|&\leq 6x^{4}+|2x^{3}|+5\\&\leq 6x^{4}+2x^{4}+5x^{4}\\&=13x^{4}\end{aligned}}$ ${\begin{aligned}|6x^{4}-2x^{3}+5|&\leq 6x^{4}+|2x^{3}|+5\\&\leq 6x^{4}+2x^{4}+5x^{4}\\&=13x^{4}\end{aligned}}$ </img>

așa că

Utilizare

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

• în matematică , este utilizată în mod obișnuit pentru a descrie cât de aproape este o serie finită aproximând o anumită funcție, în special în cazul unei serii Taylor trunchiate sau al unei dezvoltări asimptotice
• în domeniul informaticii, este utilă în analiza algoritmilor

În ambele aplicații, funcția 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ă
• asimptotica infinitezimală.

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

Asimptotica infinită

Graficele funcțiilor utilizate în mod obișnuit în analiza algoritmilor, care arată numărul de operații N în raport cu dimensiunea intrării n pentru fiecare funcție

Notația Big O este utilă atunci când se analizează eficiența algoritmilor. De exemplu, timpul (sau numărul de pași) necesar pentru a rezolva o problemă de dimensiune n poate fi găsit a fi T ( n ) = 4 n ² - 2 n + 2. Când n crește foarte mult, termenul n² ajunge să domine, astfel încât toți ceilalți termeni pot fi neglijați, de exemplu, atunci când n = 500, termenul 4n² este de 1000 de ori mai mare ca termenul 2n. Ignorarea acestuia din urmă ar avea un efect neglijabil asupra valorii expresiei pentru cele mai multe scopuri. Mai mult, coeficienții devin irelevanți dacă comparăm cu oricare alt ordin al expresiei, cum ar fi o expresie care conține un termen n³ sau n⁴. Chiar dacă T(n) = 1.000.000 n², dacă U(n) = n³, acesta din urmă îl va depăși întotdeauna pe primul când n crește mai mare decât 1.000.000 (T(1.000.000) = 1.000.000³ = 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

fie

și se spune că algoritmul are complexitate de ordinul n². 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 abuz de notație.

Asimptotica infinitezimală

Big O poate fi folosită și pentru a descrie 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, seria exponențială și două expresii ale acesteia care sunt valabile atunci când x este mic:

Nu s-a putut interpreta (eroare de sintaxă): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mrow class="MJX-TeXAtom-ORD"><mtable displaystyle="true" rowspacing="3pt"><mtr><mtd><msup><mi> <math>\begin{align} e^x &=1+x+\frac{x^2}{2!}+\frac{x^3}{3!}+\frac{x^4}{4!}+\dotsb &\text{for all } x\\ &=1+x+\frac{x^2}{2}+O(x^3) &\text{as } x\to 0\\ &=1+x+O(x^2) &\text{as } x\to 0\\ \end{align}} </mi><mrow class="MJX-TeXAtom-ORD"><mi> ${\begin{aligned}e^{x}&=1+x+{\frac {x^{2}}{2!}}+{\frac {x^{3}}{3!}}+{\frac {x^{4}}{4!}}+\dotsb &{\text{for all }}x\\&=1+x+{\frac {x^{2}}{2}}+O(x^{3})&{\text{as }}x\to 0\\&=1+x+O(x^{2})&{\text{as }}x\to 0\\\end{aligned}}$ </mi></mrow></msup></mtd><mtd><mo> ${\begin{aligned}e^{x}&=1+x+{\frac {x^{2}}{2!}}+{\frac {x^{3}}{3!}}+{\frac {x^{4}}{4!}}+\dotsb &{\text{for all }}x\\&=1+x+{\frac {x^{2}}{2}}+O(x^{3})&{\text{as }}x\to 0\\&=1+x+O(x^{2})&{\text{as }}x\to 0\\\end{aligned}}$ </mo><mn> ${\begin{aligned}e^{x}&=1+x+{\frac {x^{2}}{2!}}+{\frac {x^{3}}{3!}}+{\frac {x^{4}}{4!}}+\dotsb &{\text{for all }}x\\&=1+x+{\frac {x^{2}}{2}}+O(x^{3})&{\text{as }}x\to 0\\&=1+x+O(x^{2})&{\text{as }}x\to 0\\\end{aligned}}$ </mn><mo> ${\begin{aligned}e^{x}&=1+x+{\frac {x^{2}}{2!}}+{\frac {x^{3}}{3!}}+{\frac {x^{4}}{4!}}+\dotsb &{\text{for all }}x\\&=1+x+{\frac {x^{2}}{2}}+O(x^{3})&{\text{as }}x\to 0\\&=1+x+O(x^{2})&{\text{as }}x\to 0\\\end{aligned}}$ </mo><mi> ${\begin{aligned}e^{x}&=1+x+{\frac {x^{2}}{2!}}+{\frac {x^{3}}{3!}}+{\frac {x^{4}}{4!}}+\dotsb &{\text{for all }}x\\&=1+x+{\frac {x^{2}}{2}}+O(x^{3})&{\text{as }}x\to 0\\&=1+x+O(x^{2})&{\text{as }}x\to 0\\\end{aligned}}$ </mi><mo> ${\begin{aligned}e^{x}&=1+x+{\frac {x^{2}}{2!}}+{\frac {x^{3}}{3!}}+{\frac {x^{4}}{4!}}+\dotsb &{\text{for all }}x\\&=1+x+{\frac {x^{2}}{2}}+O(x^{3})&{\text{as }}x\to 0\\&=1+x+O(x^{2})&{\text{as }}x\to 0\\\end{aligned}}$ </mo><mrow class="MJX-TeXAtom-ORD"><mfrac><msup><mi> ${\begin{aligned}e^{x}&=1+x+{\frac {x^{2}}{2!}}+{\frac {x^{3}}{3!}}+{\frac {x^{4}}{4!}}+\dotsb &{\text{for all }}x\\&=1+x+{\frac {x^{2}}{2}}+O(x^{3})&{\text{as }}x\to 0\\&=1+x+O(x^{2})&{\text{as }}x\to 0\\\end{aligned}}$ </mi><mrow class="MJX-TeXAtom-ORD"><mn> ${\begin{aligned}e^{x}&=1+x+{\frac {x^{2}}{2!}}+{\frac {x^{3}}{3!}}+{\frac {x^{4}}{4!}}+\dotsb &{\text{for all }}x\\&=1+x+{\frac {x^{2}}{2}}+O(x^{3})&{\text{as }}x\to 0\\&=1+x+O(x^{2})&{\text{as }}x\to 0\\\end{aligned}}$ </mn></mrow></msup><mrow><mn> ${\begin{aligned}e^{x}&=1+x+{\frac {x^{2}}{2!}}+{\frac {x^{3}}{3!}}+{\frac {x^{4}}{4!}}+\dotsb &{\text{for all }}x\\&=1+x+{\frac {x^{2}}{2}}+O(x^{3})&{\text{as }}x\to 0\\&=1+x+O(x^{2})&{\text{as }}x\to 0\\\end{aligned}}$ </mn><mo> ${\begin{aligned}e^{x}&=1+x+{\frac {x^{2}}{2!}}+{\frac {x^{3}}{3!}}+{\frac {x^{4}}{4!}}+\dotsb &{\text{for all }}x\\&=1+x+{\frac {x^{2}}{2}}+O(x^{3})&{\text{as }}x\to 0\\&=1+x+O(x^{2})&{\text{as }}x\to 0\\\end{aligned}}$ </mo></mrow></mfrac></mrow><mo> ${\begin{aligned}e^{x}&=1+x+{\frac {x^{2}}{2!}}+{\frac {x^{3}}{3!}}+{\frac {x^{4}}{4!}}+\dotsb &{\text{for all }}x\\&=1+x+{\frac {x^{2}}{2}}+O(x^{3})&{\text{as }}x\to 0\\&=1+x+O(x^{2})&{\text{as }}x\to 0\\\end{aligned}}$ </mo><mrow class="MJX-TeXAtom-ORD"><mfrac><msup><mi> ${\begin{aligned}e^{x}&=1+x+{\frac {x^{2}}{2!}}+{\frac {x^{3}}{3!}}+{\frac {x^{4}}{4!}}+\dotsb &{\text{for all }}x\\&=1+x+{\frac {x^{2}}{2}}+O(x^{3})&{\text{as }}x\to 0\\&=1+x+O(x^{2})&{\text{as }}x\to 0\\\end{aligned}}$ </mi><mrow class="MJX-TeXAtom-ORD"><mn> ${\begin{aligned}e^{x}&=1+x+{\frac {x^{2}}{2!}}+{\frac {x^{3}}{3!}}+{\frac {x^{4}}{4!}}+\dotsb &{\text{for all }}x\\&=1+x+{\frac {x^{2}}{2}}+O(x^{3})&{\text{as }}x\to 0\\&=1+x+O(x^{2})&{\text{as }}x\to 0\\\end{aligned}}$ </mn></mrow></msup><mrow><mn> ${\begin{aligned}e^{x}&=1+x+{\frac {x^{2}}{2!}}+{\frac {x^{3}}{3!}}+{\frac {x^{4}}{4!}}+\dotsb &{\text{for all }}x\\&=1+x+{\frac {x^{2}}{2}}+O(x^{3})&{\text{as }}x\to 0\\&=1+x+O(x^{2})&{\text{as }}x\to 0\\\end{aligned}}$ </mn><mo> ${\begin{aligned}e^{x}&=1+x+{\frac {x^{2}}{2!}}+{\frac {x^{3}}{3!}}+{\frac {x^{4}}{4!}}+\dotsb &{\text{for all }}x\\&=1+x+{\frac {x^{2}}{2}}+O(x^{3})&{\text{as }}x\to 0\\&=1+x+O(x^{2})&{\text{as }}x\to 0\\\end{aligned}}$ </mo></mrow></mfrac></mrow><mo> ${\begin{aligned}e^{x}&=1+x+{\frac {x^{2}}{2!}}+{\frac {x^{3}}{3!}}+{\frac {x^{4}}{4!}}+\dotsb &{\text{for all }}x\\&=1+x+{\frac {x^{2}}{2}}+O(x^{3})&{\text{as }}x\to 0\\&=1+x+O(x^{2})&{\text{as }}x\to 0\\\end{aligned}}$ </mo><mrow class="MJX-TeXAtom-ORD"><mfrac><msup><mi> ${\begin{aligned}e^{x}&=1+x+{\frac {x^{2}}{2!}}+{\frac {x^{3}}{3!}}+{\frac {x^{4}}{4!}}+\dotsb &{\text{for all }}x\\&=1+x+{\frac {x^{2}}{2}}+O(x^{3})&{\text{as }}x\to 0\\&=1+x+O(x^{2})&{\text{as }}x\to 0\\\end{aligned}}$ </mi><mrow class="MJX-TeXAtom-ORD"><mn> ${\begin{aligned}e^{x}&=1+x+{\frac {x^{2}}{2!}}+{\frac {x^{3}}{3!}}+{\frac {x^{4}}{4!}}+\dotsb &{\text{for all }}x\\&=1+x+{\frac {x^{2}}{2}}+O(x^{3})&{\text{as }}x\to 0\\&=1+x+O(x^{2})&{\text{as }}x\to 0\\\end{aligned}}$ </mn></mrow></msup><mrow><mn> ${\begin{aligned}e^{x}&=1+x+{\frac {x^{2}}{2!}}+{\frac {x^{3}}{3!}}+{\frac {x^{4}}{4!}}+\dotsb &{\text{for all }}x\\&=1+x+{\frac {x^{2}}{2}}+O(x^{3})&{\text{as }}x\to 0\\&=1+x+O(x^{2})&{\text{as }}x\to 0\\\end{aligned}}$ </mn><mo> ${\begin{aligned}e^{x}&=1+x+{\frac {x^{2}}{2!}}+{\frac {x^{3}}{3!}}+{\frac {x^{4}}{4!}}+\dotsb &{\text{for all }}x\\&=1+x+{\frac {x^{2}}{2}}+O(x^{3})&{\text{as }}x\to 0\\&=1+x+O(x^{2})&{\text{as }}x\to 0\\\end{aligned}}$ </mo></mrow></mfrac></mrow><mo> ${\begin{aligned}e^{x}&=1+x+{\frac {x^{2}}{2!}}+{\frac {x^{3}}{3!}}+{\frac {x^{4}}{4!}}+\dotsb &{\text{for all }}x\\&=1+x+{\frac {x^{2}}{2}}+O(x^{3})&{\text{as }}x\to 0\\&=1+x+O(x^{2})&{\text{as }}x\to 0\\\end{aligned}}$ </mo><mo> ${\begin{aligned}e^{x}&=1+x+{\frac {x^{2}}{2!}}+{\frac {x^{3}}{3!}}+{\frac {x^{4}}{4!}}+\dotsb &{\text{for all }}x\\&=1+x+{\frac {x^{2}}{2}}+O(x^{3})&{\text{as }}x\to 0\\&=1+x+O(x^{2})&{\text{as }}x\to 0\\\end{aligned}}$ </mo></mtd><mtd><mrow class="MJX-TeXAtom-ORD"><mtext> ${\begin{aligned}e^{x}&=1+x+{\frac {x^{2}}{2!}}+{\frac {x^{3}}{3!}}+{\frac {x^{4}}{4!}}+\dotsb &{\text{for all }}x\\&=1+x+{\frac {x^{2}}{2}}+O(x^{3})&{\text{as }}x\to 0\\&=1+x+O(x^{2})&{\text{as }}x\to 0\\\end{aligned}}$ </mtext></mrow><mi> ${\begin{aligned}e^{x}&=1+x+{\frac {x^{2}}{2!}}+{\frac {x^{3}}{3!}}+{\frac {x^{4}}{4!}}+\dotsb &{\text{for all }}x\\&=1+x+{\frac {x^{2}}{2}}+O(x^{3})&{\text{as }}x\to 0\\&=1+x+O(x^{2})&{\text{as }}x\to 0\\\end{aligned}}$ </mi></mtd></mtr><mtr><mtd><mo> ${\begin{aligned}e^{x}&=1+x+{\frac {x^{2}}{2!}}+{\frac {x^{3}}{3!}}+{\frac {x^{4}}{4!}}+\dotsb &{\text{for all }}x\\&=1+x+{\frac {x^{2}}{2}}+O(x^{3})&{\text{as }}x\to 0\\&=1+x+O(x^{2})&{\text{as }}x\to 0\\\end{aligned}}$ </mo><mn> ${\begin{aligned}e^{x}&=1+x+{\frac {x^{2}}{2!}}+{\frac {x^{3}}{3!}}+{\frac {x^{4}}{4!}}+\dotsb &{\text{for all }}x\\&=1+x+{\frac {x^{2}}{2}}+O(x^{3})&{\text{as }}x\to 0\\&=1+x+O(x^{2})&{\text{as }}x\to 0\\\end{aligned}}$ </mn><mo> ${\begin{aligned}e^{x}&=1+x+{\frac {x^{2}}{2!}}+{\frac {x^{3}}{3!}}+{\frac {x^{4}}{4!}}+\dotsb &{\text{for all }}x\\&=1+x+{\frac {x^{2}}{2}}+O(x^{3})&{\text{as }}x\to 0\\&=1+x+O(x^{2})&{\text{as }}x\to 0\\\end{aligned}}$ </mo><mi> ${\begin{aligned}e^{x}&=1+x+{\frac {x^{2}}{2!}}+{\frac {x^{3}}{3!}}+{\frac {x^{4}}{4!}}+\dotsb &{\text{for all }}x\\&=1+x+{\frac {x^{2}}{2}}+O(x^{3})&{\text{as }}x\to 0\\&=1+x+O(x^{2})&{\text{as }}x\to 0\\\end{aligned}}$ </mi><mo> ${\begin{aligned}e^{x}&=1+x+{\frac {x^{2}}{2!}}+{\frac {x^{3}}{3!}}+{\frac {x^{4}}{4!}}+\dotsb &{\text{for all }}x\\&=1+x+{\frac {x^{2}}{2}}+O(x^{3})&{\text{as }}x\to 0\\&=1+x+O(x^{2})&{\text{as }}x\to 0\\\end{aligned}}$ </mo><mrow class="MJX-TeXAtom-ORD"><mfrac><msup><mi> ${\begin{aligned}e^{x}&=1+x+{\frac {x^{2}}{2!}}+{\frac {x^{3}}{3!}}+{\frac {x^{4}}{4!}}+\dotsb &{\text{for all }}x\\&=1+x+{\frac {x^{2}}{2}}+O(x^{3})&{\text{as }}x\to 0\\&=1+x+O(x^{2})&{\text{as }}x\to 0\\\end{aligned}}$ </mi><mrow class="MJX-TeXAtom-ORD"><mn> ${\begin{aligned}e^{x}&=1+x+{\frac {x^{2}}{2!}}+{\frac {x^{3}}{3!}}+{\frac {x^{4}}{4!}}+\dotsb &{\text{for all }}x\\&=1+x+{\frac {x^{2}}{2}}+O(x^{3})&{\text{as }}x\to 0\\&=1+x+O(x^{2})&{\text{as }}x\to 0\\\end{aligned}}$ </mn></mrow></msup><mn> ${\begin{aligned}e^{x}&=1+x+{\frac {x^{2}}{2!}}+{\frac {x^{3}}{3!}}+{\frac {x^{4}}{4!}}+\dotsb &{\text{for all }}x\\&=1+x+{\frac {x^{2}}{2}}+O(x^{3})&{\text{as }}x\to 0\\&=1+x+O(x^{2})&{\text{as }}x\to 0\\\end{aligned}}$ </mn></mfrac></mrow><mo> ${\begin{aligned}e^{x}&=1+x+{\frac {x^{2}}{2!}}+{\frac {x^{3}}{3!}}+{\frac {x^{4}}{4!}}+\dotsb &{\text{for all }}x\\&=1+x+{\frac {x^{2}}{2}}+O(x^{3})&{\text{as }}x\to 0\\&=1+x+O(x^{2})&{\text{as }}x\to 0\\\end{aligned}}$ </mo><mi> ${\begin{aligned}e^{x}&=1+x+{\frac {x^{2}}{2!}}+{\frac {x^{3}}{3!}}+{\frac {x^{4}}{4!}}+\dotsb &{\text{for all }}x\\&=1+x+{\frac {x^{2}}{2}}+O(x^{3})&{\text{as }}x\to 0\\&=1+x+O(x^{2})&{\text{as }}x\to 0\\\end{aligned}}$ </mi><mo stretchy="false"> ${\begin{aligned}e^{x}&=1+x+{\frac {x^{2}}{2!}}+{\frac {x^{3}}{3!}}+{\frac {x^{4}}{4!}}+\dotsb &{\text{for all }}x\\&=1+x+{\frac {x^{2}}{2}}+O(x^{3})&{\text{as }}x\to 0\\&=1+x+O(x^{2})&{\text{as }}x\to 0\\\end{aligned}}$ </mo><msup><mi> ${\begin{aligned}e^{x}&=1+x+{\frac {x^{2}}{2!}}+{\frac {x^{3}}{3!}}+{\frac {x^{4}}{4!}}+\dotsb &{\text{for all }}x\\&=1+x+{\frac {x^{2}}{2}}+O(x^{3})&{\text{as }}x\to 0\\&=1+x+O(x^{2})&{\text{as }}x\to 0\\\end{aligned}}$ </mi><mrow class="MJX-TeXAtom-ORD"><mn> ${\begin{aligned}e^{x}&=1+x+{\frac {x^{2}}{2!}}+{\frac {x^{3}}{3!}}+{\frac {x^{4}}{4!}}+\dotsb &{\text{for all }}x\\&=1+x+{\frac {x^{2}}{2}}+O(x^{3})&{\text{as }}x\to 0\\&=1+x+O(x^{2})&{\text{as }}x\to 0\\\end{aligned}}$ </mn></mrow></msup><mo stretchy="false"> ${\begin{aligned}e^{x}&=1+x+{\frac {x^{2}}{2!}}+{\frac {x^{3}}{3!}}+{\frac {x^{4}}{4!}}+\dotsb &{\text{for all }}x\\&=1+x+{\frac {x^{2}}{2}}+O(x^{3})&{\text{as }}x\to 0\\&=1+x+O(x^{2})&{\text{as }}x\to 0\\\end{aligned}}$ </mo></mtd><mtd><mrow class="MJX-TeXAtom-ORD"><mtext> ${\begin{aligned}e^{x}&=1+x+{\frac {x^{2}}{2!}}+{\frac {x^{3}}{3!}}+{\frac {x^{4}}{4!}}+\dotsb &{\text{for all }}x\\&=1+x+{\frac {x^{2}}{2}}+O(x^{3})&{\text{as }}x\to 0\\&=1+x+O(x^{2})&{\text{as }}x\to 0\\\end{aligned}}$ </mtext></mrow><mi> ${\begin{aligned}e^{x}&=1+x+{\frac {x^{2}}{2!}}+{\frac {x^{3}}{3!}}+{\frac {x^{4}}{4!}}+\dotsb &{\text{for all }}x\\&=1+x+{\frac {x^{2}}{2}}+O(x^{3})&{\text{as }}x\to 0\\&=1+x+O(x^{2})&{\text{as }}x\to 0\\\end{aligned}}$ </mi><mo stretchy="false"> ${\begin{aligned}e^{x}&=1+x+{\frac {x^{2}}{2!}}+{\frac {x^{3}}{3!}}+{\frac {x^{4}}{4!}}+\dotsb &{\text{for all }}x\\&=1+x+{\frac {x^{2}}{2}}+O(x^{3})&{\text{as }}x\to 0\\&=1+x+O(x^{2})&{\text{as }}x\to 0\\\end{aligned}}$ </mo><mn> ${\begin{aligned}e^{x}&=1+x+{\frac {x^{2}}{2!}}+{\frac {x^{3}}{3!}}+{\frac {x^{4}}{4!}}+\dotsb &{\text{for all }}x\\&=1+x+{\frac {x^{2}}{2}}+O(x^{3})&{\text{as }}x\to 0\\&=1+x+O(x^{2})&{\text{as }}x\to 0\\\end{aligned}}$ </mn></mtd></mtr><mtr><mtd><mo> ${\begin{aligned}e^{x}&=1+x+{\frac {x^{2}}{2!}}+{\frac {x^{3}}{3!}}+{\frac {x^{4}}{4!}}+\dotsb &{\text{for all }}x\\&=1+x+{\frac {x^{2}}{2}}+O(x^{3})&{\text{as }}x\to 0\\&=1+x+O(x^{2})&{\text{as }}x\to 0\\\end{aligned}}$ </mo><mn> ${\begin{aligned}e^{x}&=1+x+{\frac {x^{2}}{2!}}+{\frac {x^{3}}{3!}}+{\frac {x^{4}}{4!}}+\dotsb &{\text{for all }}x\\&=1+x+{\frac {x^{2}}{2}}+O(x^{3})&{\text{as }}x\to 0\\&=1+x+O(x^{2})&{\text{as }}x\to 0\\\end{aligned}}$ </mn><mo> ${\begin{aligned}e^{x}&=1+x+{\frac {x^{2}}{2!}}+{\frac {x^{3}}{3!}}+{\frac {x^{4}}{4!}}+\dotsb &{\text{for all }}x\\&=1+x+{\frac {x^{2}}{2}}+O(x^{3})&{\text{as }}x\to 0\\&=1+x+O(x^{2})&{\text{as }}x\to 0\\\end{aligned}}$ </mo><mi> ${\begin{aligned}e^{x}&=1+x+{\frac {x^{2}}{2!}}+{\frac {x^{3}}{3!}}+{\frac {x^{4}}{4!}}+\dotsb &{\text{for all }}x\\&=1+x+{\frac {x^{2}}{2}}+O(x^{3})&{\text{as }}x\to 0\\&=1+x+O(x^{2})&{\text{as }}x\to 0\\\end{aligned}}$ </mi><mo> ${\begin{aligned}e^{x}&=1+x+{\frac {x^{2}}{2!}}+{\frac {x^{3}}{3!}}+{\frac {x^{4}}{4!}}+\dotsb &{\text{for all }}x\\&=1+x+{\frac {x^{2}}{2}}+O(x^{3})&{\text{as }}x\to 0\\&=1+x+O(x^{2})&{\text{as }}x\to 0\\\end{aligned}}$ </mo><mi> ${\begin{aligned}e^{x}&=1+x+{\frac {x^{2}}{2!}}+{\frac {x^{3}}{3!}}+{\frac {x^{4}}{4!}}+\dotsb &{\text{for all }}x\\&=1+x+{\frac {x^{2}}{2}}+O(x^{3})&{\text{as }}x\to 0\\&=1+x+O(x^{2})&{\text{as }}x\to 0\\\end{aligned}}$ </mi><mo stretchy="false"> ${\begin{aligned}e^{x}&=1+x+{\frac {x^{2}}{2!}}+{\frac {x^{3}}{3!}}+{\frac {x^{4}}{4!}}+\dotsb &{\text{for all }}x\\&=1+x+{\frac {x^{2}}{2}}+O(x^{3})&{\text{as }}x\to 0\\&=1+x+O(x^{2})&{\text{as }}x\to 0\\\end{aligned}}$ </mo><msup><mi> ${\begin{aligned}e^{x}&=1+x+{\frac {x^{2}}{2!}}+{\frac {x^{3}}{3!}}+{\frac {x^{4}}{4!}}+\dotsb &{\text{for all }}x\\&=1+x+{\frac {x^{2}}{2}}+O(x^{3})&{\text{as }}x\to 0\\&=1+x+O(x^{2})&{\text{as }}x\to 0\\\end{aligned}}$ </mi><mrow class="MJX-TeXAtom-ORD"><mn> ${\begin{aligned}e^{x}&=1+x+{\frac {x^{2}}{2!}}+{\frac {x^{3}}{3!}}+{\frac {x^{4}}{4!}}+\dotsb &{\text{for all }}x\\&=1+x+{\frac {x^{2}}{2}}+O(x^{3})&{\text{as }}x\to 0\\&=1+x+O(x^{2})&{\text{as }}x\to 0\\\end{aligned}}$ </mn></mrow></msup><mo stretchy="false"> ${\begin{aligned}e^{x}&=1+x+{\frac {x^{2}}{2!}}+{\frac {x^{3}}{3!}}+{\frac {x^{4}}{4!}}+\dotsb &{\text{for all }}x\\&=1+x+{\frac {x^{2}}{2}}+O(x^{3})&{\text{as }}x\to 0\\&=1+x+O(x^{2})&{\text{as }}x\to 0\\\end{aligned}}$ </mo></mtd><mtd><mrow class="MJX-TeXAtom-ORD"><mtext> ${\begin{aligned}e^{x}&=1+x+{\frac {x^{2}}{2!}}+{\frac {x^{3}}{3!}}+{\frac {x^{4}}{4!}}+\dotsb &{\text{for all }}x\\&=1+x+{\frac {x^{2}}{2}}+O(x^{3})&{\text{as }}x\to 0\\&=1+x+O(x^{2})&{\text{as }}x\to 0\\\end{aligned}}$ </mtext></mrow><mi> ${\begin{aligned}e^{x}&=1+x+{\frac {x^{2}}{2!}}+{\frac {x^{3}}{3!}}+{\frac {x^{4}}{4!}}+\dotsb &{\text{for all }}x\\&=1+x+{\frac {x^{2}}{2}}+O(x^{3})&{\text{as }}x\to 0\\&=1+x+O(x^{2})&{\text{as }}x\to 0\\\end{aligned}}$ </mi><mo stretchy="false"> ${\begin{aligned}e^{x}&=1+x+{\frac {x^{2}}{2!}}+{\frac {x^{3}}{3!}}+{\frac {x^{4}}{4!}}+\dotsb &{\text{for all }}x\\&=1+x+{\frac {x^{2}}{2}}+O(x^{3})&{\text{as }}x\to 0\\&=1+x+O(x^{2})&{\text{as }}x\to 0\\\end{aligned}}$ </mo><mn> ${\begin{aligned}e^{x}&=1+x+{\frac {x^{2}}{2!}}+{\frac {x^{3}}{3!}}+{\frac {x^{4}}{4!}}+\dotsb &{\text{for all }}x\\&=1+x+{\frac {x^{2}}{2}}+O(x^{3})&{\text{as }}x\to 0\\&=1+x+O(x^{2})&{\text{as }}x\to 0\\\end{aligned}}$ </mn></mtd></mtr></mtable></mrow></mstyle></mrow> </math>${\begin{aligned}e^{x}&=1+x+{\frac {x^{2}}{2!}}+{\frac {x^{3}}{3!}}+{\frac {x^{4}}{4!}}+\dotsb &{\text{for all }}x\\&=1+x+{\frac {x^{2}}{2}}+O(x^{3})&{\text{as }}x\to 0\\&=1+x+O(x^{2})&{\text{as }}x\to 0\\\end{aligned}}$ ${\begin{aligned}e^{x}&=1+x+{\frac {x^{2}}{2!}}+{\frac {x^{3}}{3!}}+{\frac {x^{4}}{4!}}+\dotsb &{\text{for all }}x\\&=1+x+{\frac {x^{2}}{2}}+O(x^{3})&{\text{as }}x\to 0\\&=1+x+O(x^{2})&{\text{as }}x\to 0\\\end{aligned}}$ </img>

Cea de a doua expresie (cea cu O(x³)) înseamnă că valoarea absolută a erorii e^x - (1 + x²/2) este de cel mult o constantă înmulțită cu | x³ | când x este suficient de aproape de 0.

Proprietăți

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

<mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mi> $f(n)=9\log n+5(\log n)^{4}+3n^{2}+2n^{3}=O(n^{3})\qquad {\text{as }}n\to \infty .$ </mi><mo stretchy="false"> $f(n)=9\log n+5(\log n)^{4}+3n^{2}+2n^{3}=O(n^{3})\qquad {\text{as }}n\to \infty .$ </mo><mi> $f(n)=9\log n+5(\log n)^{4}+3n^{2}+2n^{3}=O(n^{3})\qquad {\text{as }}n\to \infty .$ </mi><mo stretchy="false"> $f(n)=9\log n+5(\log n)^{4}+3n^{2}+2n^{3}=O(n^{3})\qquad {\text{as }}n\to \infty .$ </mo><mo> $f(n)=9\log n+5(\log n)^{4}+3n^{2}+2n^{3}=O(n^{3})\qquad {\text{as }}n\to \infty .$ </mo><mn> $f(n)=9\log n+5(\log n)^{4}+3n^{2}+2n^{3}=O(n^{3})\qquad {\text{as }}n\to \infty .$ </mn><mi> $f(n)=9\log n+5(\log n)^{4}+3n^{2}+2n^{3}=O(n^{3})\qquad {\text{as }}n\to \infty .$ </mi><mo> $f(n)=9\log n+5(\log n)^{4}+3n^{2}+2n^{3}=O(n^{3})\qquad {\text{as }}n\to \infty .$ </mo><mi> $f(n)=9\log n+5(\log n)^{4}+3n^{2}+2n^{3}=O(n^{3})\qquad {\text{as }}n\to \infty .$ </mi><mo> $f(n)=9\log n+5(\log n)^{4}+3n^{2}+2n^{3}=O(n^{3})\qquad {\text{as }}n\to \infty .$ </mo><mn> $f(n)=9\log n+5(\log n)^{4}+3n^{2}+2n^{3}=O(n^{3})\qquad {\text{as }}n\to \infty .$ </mn><mo stretchy="false"> $f(n)=9\log n+5(\log n)^{4}+3n^{2}+2n^{3}=O(n^{3})\qquad {\text{as }}n\to \infty .$ </mo><mi> $f(n)=9\log n+5(\log n)^{4}+3n^{2}+2n^{3}=O(n^{3})\qquad {\text{as }}n\to \infty .$ </mi><mo> $f(n)=9\log n+5(\log n)^{4}+3n^{2}+2n^{3}=O(n^{3})\qquad {\text{as }}n\to \infty .$ </mo><mi> $f(n)=9\log n+5(\log n)^{4}+3n^{2}+2n^{3}=O(n^{3})\qquad {\text{as }}n\to \infty .$ </mi><msup><mo stretchy="false"> $f(n)=9\log n+5(\log n)^{4}+3n^{2}+2n^{3}=O(n^{3})\qquad {\text{as }}n\to \infty .$ </mo><mrow class="MJX-TeXAtom-ORD"><mn> $f(n)=9\log n+5(\log n)^{4}+3n^{2}+2n^{3}=O(n^{3})\qquad {\text{as }}n\to \infty .$ </mn></mrow></msup><mo> $f(n)=9\log n+5(\log n)^{4}+3n^{2}+2n^{3}=O(n^{3})\qquad {\text{as }}n\to \infty .$ </mo><mn> $f(n)=9\log n+5(\log n)^{4}+3n^{2}+2n^{3}=O(n^{3})\qquad {\text{as }}n\to \infty .$ </mn><msup><mi> $f(n)=9\log n+5(\log n)^{4}+3n^{2}+2n^{3}=O(n^{3})\qquad {\text{as }}n\to \infty .$ </mi><mrow class="MJX-TeXAtom-ORD"><mn> $f(n)=9\log n+5(\log n)^{4}+3n^{2}+2n^{3}=O(n^{3})\qquad {\text{as }}n\to \infty .$ </mn></mrow></msup><mo> $f(n)=9\log n+5(\log n)^{4}+3n^{2}+2n^{3}=O(n^{3})\qquad {\text{as }}n\to \infty .$ </mo><mn> $f(n)=9\log n+5(\log n)^{4}+3n^{2}+2n^{3}=O(n^{3})\qquad {\text{as }}n\to \infty .$ </mn><msup><mi> $f(n)=9\log n+5(\log n)^{4}+3n^{2}+2n^{3}=O(n^{3})\qquad {\text{as }}n\to \infty .$ </mi><mrow class="MJX-TeXAtom-ORD"><mn> $f(n)=9\log n+5(\log n)^{4}+3n^{2}+2n^{3}=O(n^{3})\qquad {\text{as }}n\to \infty .$ </mn></mrow></msup><mo> $f(n)=9\log n+5(\log n)^{4}+3n^{2}+2n^{3}=O(n^{3})\qquad {\text{as }}n\to \infty .$ </mo><mi> $f(n)=9\log n+5(\log n)^{4}+3n^{2}+2n^{3}=O(n^{3})\qquad {\text{as }}n\to \infty .$ </mi><mo stretchy="false"> $f(n)=9\log n+5(\log n)^{4}+3n^{2}+2n^{3}=O(n^{3})\qquad {\text{as }}n\to \infty .$ </mo><msup><mi> $f(n)=9\log n+5(\log n)^{4}+3n^{2}+2n^{3}=O(n^{3})\qquad {\text{as }}n\to \infty .$ </mi><mrow class="MJX-TeXAtom-ORD"><mn> $f(n)=9\log n+5(\log n)^{4}+3n^{2}+2n^{3}=O(n^{3})\qquad {\text{as }}n\to \infty .$ </mn></mrow></msup><mo stretchy="false"> $f(n)=9\log n+5(\log n)^{4}+3n^{2}+2n^{3}=O(n^{3})\qquad {\text{as }}n\to \infty .$ </mo><mrow class="MJX-TeXAtom-ORD"><mtext> $f(n)=9\log n+5(\log n)^{4}+3n^{2}+2n^{3}=O(n^{3})\qquad {\text{as }}n\to \infty .$ </mtext></mrow><mi> $f(n)=9\log n+5(\log n)^{4}+3n^{2}+2n^{3}=O(n^{3})\qquad {\text{as }}n\to \infty .$ </mi><mo stretchy="false"> $f(n)=9\log n+5(\log n)^{4}+3n^{2}+2n^{3}=O(n^{3})\qquad {\text{as }}n\to \infty .$ </mo><mi mathvariant="normal"> $f(n)=9\log n+5(\log n)^{4}+3n^{2}+2n^{3}=O(n^{3})\qquad {\text{as }}n\to \infty .$ </mi><mo> $f(n)=9\log n+5(\log n)^{4}+3n^{2}+2n^{3}=O(n^{3})\qquad {\text{as }}n\to \infty .$ </mo></mstyle></mrow> $f(n)=9\log n+5(\log n)^{4}+3n^{2}+2n^{3}=O(n^{3})\qquad {\text{as }}n\to \infty .$ ${\displaystyle }$$f(n)=9\log n+5(\log n)^{4}+3n^{2}+2n^{3}=O(n^{3})\qquad {\text{as }}n\to \infty .$ $f(n)=9\log n+5(\log n)^{4}+3n^{2}+2n^{3}=O(n^{3})\qquad {\text{as }}n\to \infty .$ </img>

În special, dacă o funcție poate fi legată de un polinom în n, atunci când n tinde spre infinit, se pot ignora termenii de grad mai mic ai polinomului. De asemenea, mulțimile O(n^c) și O(cⁿ) 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 n^c pentru oricare c se numește superpolinomială. Una care crește mai lent decât orice funcție exponențială de forma cⁿ 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 numerelor întregi și funcția n^{log n}.

Se poate ignora orice putere a lui n din interiorul logaritmilor. Mulțimea O (log n) este exact același cu O (log n^c). Logaritmii diferă numai printr-un factor constant (întrucât log n^c = 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, 2ⁿ nu este același lucru cu 3ⁿ.

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 n², înlocuirea n cu cn înseamnă că algoritmul rulează în timp de ordinul lui c²n², iar notația Big O ignoră constanta c². Aceasta se poate scrie ca c²n² = O(n²). Dacă, totuși, un algoritm rulează în timp de ordinul lui 2ⁿ, înlocuirea lui n cu cn dă timp de ordinul 2^cn = (2^c)ⁿ. Aceasta nu este echivalentă cu 2ⁿ în general. Schimbarea variabilelor poate afecta, de asemenea, ordinul algoritmului rezultat. De exemplu, dacă timpul de execuție al algoritmului este O(n) atunci când este măsurat în termeni de număr n de cifre al unui număr de intrare x, timpul său de execuție este O(log x) ca funcție de numărul de intrare x însuși, deoarece n = O(log x).

Produsul

Nu s-a putut interpreta (eroare de sintaxă): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><msub><mi> <math> f_1 = O(g_1) \text{ and } f_2 = O(g_2)\, \Rightarrow f_1 f_2 = O(g_1 g_2)} </mi><mrow class="MJX-TeXAtom-ORD"><mn> $f_{1}=O(g_{1}){\text{ and }}f_{2}=O(g_{2})\,\Rightarrow f_{1}f_{2}=O(g_{1}g_{2})$ </mn></mrow></msub><mo> $f_{1}=O(g_{1}){\text{ and }}f_{2}=O(g_{2})\,\Rightarrow f_{1}f_{2}=O(g_{1}g_{2})$ </mo><mi> $f_{1}=O(g_{1}){\text{ and }}f_{2}=O(g_{2})\,\Rightarrow f_{1}f_{2}=O(g_{1}g_{2})$ </mi><mo stretchy="false"> $f_{1}=O(g_{1}){\text{ and }}f_{2}=O(g_{2})\,\Rightarrow f_{1}f_{2}=O(g_{1}g_{2})$ </mo><msub><mi> $f_{1}=O(g_{1}){\text{ and }}f_{2}=O(g_{2})\,\Rightarrow f_{1}f_{2}=O(g_{1}g_{2})$ </mi><mrow class="MJX-TeXAtom-ORD"><mn> $f_{1}=O(g_{1}){\text{ and }}f_{2}=O(g_{2})\,\Rightarrow f_{1}f_{2}=O(g_{1}g_{2})$ </mn></mrow></msub><mo stretchy="false"> $f_{1}=O(g_{1}){\text{ and }}f_{2}=O(g_{2})\,\Rightarrow f_{1}f_{2}=O(g_{1}g_{2})$ </mo><mrow class="MJX-TeXAtom-ORD"><mtext> $f_{1}=O(g_{1}){\text{ and }}f_{2}=O(g_{2})\,\Rightarrow f_{1}f_{2}=O(g_{1}g_{2})$ </mtext></mrow><msub><mi> $f_{1}=O(g_{1}){\text{ and }}f_{2}=O(g_{2})\,\Rightarrow f_{1}f_{2}=O(g_{1}g_{2})$ </mi><mrow class="MJX-TeXAtom-ORD"><mn> $f_{1}=O(g_{1}){\text{ and }}f_{2}=O(g_{2})\,\Rightarrow f_{1}f_{2}=O(g_{1}g_{2})$ </mn></mrow></msub><mo> $f_{1}=O(g_{1}){\text{ and }}f_{2}=O(g_{2})\,\Rightarrow f_{1}f_{2}=O(g_{1}g_{2})$ </mo><mi> $f_{1}=O(g_{1}){\text{ and }}f_{2}=O(g_{2})\,\Rightarrow f_{1}f_{2}=O(g_{1}g_{2})$ </mi><mo stretchy="false"> $f_{1}=O(g_{1}){\text{ and }}f_{2}=O(g_{2})\,\Rightarrow f_{1}f_{2}=O(g_{1}g_{2})$ </mo><msub><mi> $f_{1}=O(g_{1}){\text{ and }}f_{2}=O(g_{2})\,\Rightarrow f_{1}f_{2}=O(g_{1}g_{2})$ </mi><mrow class="MJX-TeXAtom-ORD"><mn> $f_{1}=O(g_{1}){\text{ and }}f_{2}=O(g_{2})\,\Rightarrow f_{1}f_{2}=O(g_{1}g_{2})$ </mn></mrow></msub><mo stretchy="false"> $f_{1}=O(g_{1}){\text{ and }}f_{2}=O(g_{2})\,\Rightarrow f_{1}f_{2}=O(g_{1}g_{2})$ </mo><mo stretchy="false"> $f_{1}=O(g_{1}){\text{ and }}f_{2}=O(g_{2})\,\Rightarrow f_{1}f_{2}=O(g_{1}g_{2})$ </mo><msub><mi> $f_{1}=O(g_{1}){\text{ and }}f_{2}=O(g_{2})\,\Rightarrow f_{1}f_{2}=O(g_{1}g_{2})$ </mi><mrow class="MJX-TeXAtom-ORD"><mn> $f_{1}=O(g_{1}){\text{ and }}f_{2}=O(g_{2})\,\Rightarrow f_{1}f_{2}=O(g_{1}g_{2})$ </mn></mrow></msub><msub><mi> $f_{1}=O(g_{1}){\text{ and }}f_{2}=O(g_{2})\,\Rightarrow f_{1}f_{2}=O(g_{1}g_{2})$ </mi><mrow class="MJX-TeXAtom-ORD"><mn> $f_{1}=O(g_{1}){\text{ and }}f_{2}=O(g_{2})\,\Rightarrow f_{1}f_{2}=O(g_{1}g_{2})$ </mn></mrow></msub><mo> $f_{1}=O(g_{1}){\text{ and }}f_{2}=O(g_{2})\,\Rightarrow f_{1}f_{2}=O(g_{1}g_{2})$ </mo><mi> $f_{1}=O(g_{1}){\text{ and }}f_{2}=O(g_{2})\,\Rightarrow f_{1}f_{2}=O(g_{1}g_{2})$ </mi><mo stretchy="false"> $f_{1}=O(g_{1}){\text{ and }}f_{2}=O(g_{2})\,\Rightarrow f_{1}f_{2}=O(g_{1}g_{2})$ </mo><msub><mi> $f_{1}=O(g_{1}){\text{ and }}f_{2}=O(g_{2})\,\Rightarrow f_{1}f_{2}=O(g_{1}g_{2})$ </mi><mrow class="MJX-TeXAtom-ORD"><mn> $f_{1}=O(g_{1}){\text{ and }}f_{2}=O(g_{2})\,\Rightarrow f_{1}f_{2}=O(g_{1}g_{2})$ </mn></mrow></msub><msub><mi> $f_{1}=O(g_{1}){\text{ and }}f_{2}=O(g_{2})\,\Rightarrow f_{1}f_{2}=O(g_{1}g_{2})$ </mi><mrow class="MJX-TeXAtom-ORD"><mn> $f_{1}=O(g_{1}){\text{ and }}f_{2}=O(g_{2})\,\Rightarrow f_{1}f_{2}=O(g_{1}g_{2})$ </mn></mrow></msub><mo stretchy="false"> $f_{1}=O(g_{1}){\text{ and }}f_{2}=O(g_{2})\,\Rightarrow f_{1}f_{2}=O(g_{1}g_{2})$ </mo></mstyle></mrow> </math>$f_{1}=O(g_{1}){\text{ and }}f_{2}=O(g_{2})\,\Rightarrow f_{1}f_{2}=O(g_{1}g_{2})$ $f_{1}=O(g_{1}){\text{ and }}f_{2}=O(g_{2})\,\Rightarrow f_{1}f_{2}=O(g_{1}g_{2})$ </img>

Nu s-a putut interpreta (eroare de sintaxă): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mi> <math>f\cdot O(g) = O(f g)} </mi><mo> $f\cdot O(g)=O(fg)$ </mo><mi> $f\cdot O(g)=O(fg)$ </mi><mo stretchy="false"> $f\cdot O(g)=O(fg)$ </mo><mi> $f\cdot O(g)=O(fg)$ </mi><mo stretchy="false"> $f\cdot O(g)=O(fg)$ </mo><mo> $f\cdot O(g)=O(fg)$ </mo><mi> $f\cdot O(g)=O(fg)$ </mi><mo stretchy="false"> $f\cdot O(g)=O(fg)$ </mo><mi> $f\cdot O(g)=O(fg)$ </mi><mi> $f\cdot O(g)=O(fg)$ </mi><mo stretchy="false"> $f\cdot O(g)=O(fg)$ </mo></mstyle></mrow> </math>$f\cdot O(g)=O(fg)$ $f\cdot O(g)=O(fg)$ </img>

Suma

Nu s-a putut interpreta (eroare de sintaxă): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><msub><mi> <math> f_1 = O(g_1) \text{ and } f_2= O(g_2)\, \Rightarrow f_1 + f_2 = O(max(g_1, g_2))} </mi><mrow class="MJX-TeXAtom-ORD"><mn> $f_{1}=O(g_{1}){\text{ and }}f_{2}=O(g_{2})\,\Rightarrow f_{1}+f_{2}=O(max(g_{1},g_{2}))$ </mn></mrow></msub><mo> $f_{1}=O(g_{1}){\text{ and }}f_{2}=O(g_{2})\,\Rightarrow f_{1}+f_{2}=O(max(g_{1},g_{2}))$ </mo><mi> $f_{1}=O(g_{1}){\text{ and }}f_{2}=O(g_{2})\,\Rightarrow f_{1}+f_{2}=O(max(g_{1},g_{2}))$ </mi><mo stretchy="false"> $f_{1}=O(g_{1}){\text{ and }}f_{2}=O(g_{2})\,\Rightarrow f_{1}+f_{2}=O(max(g_{1},g_{2}))$ </mo><msub><mi> $f_{1}=O(g_{1}){\text{ and }}f_{2}=O(g_{2})\,\Rightarrow f_{1}+f_{2}=O(max(g_{1},g_{2}))$ </mi><mrow class="MJX-TeXAtom-ORD"><mn> $f_{1}=O(g_{1}){\text{ and }}f_{2}=O(g_{2})\,\Rightarrow f_{1}+f_{2}=O(max(g_{1},g_{2}))$ </mn></mrow></msub><mo stretchy="false"> $f_{1}=O(g_{1}){\text{ and }}f_{2}=O(g_{2})\,\Rightarrow f_{1}+f_{2}=O(max(g_{1},g_{2}))$ </mo><mrow class="MJX-TeXAtom-ORD"><mtext> $f_{1}=O(g_{1}){\text{ and }}f_{2}=O(g_{2})\,\Rightarrow f_{1}+f_{2}=O(max(g_{1},g_{2}))$ </mtext></mrow><msub><mi> $f_{1}=O(g_{1}){\text{ and }}f_{2}=O(g_{2})\,\Rightarrow f_{1}+f_{2}=O(max(g_{1},g_{2}))$ </mi><mrow class="MJX-TeXAtom-ORD"><mn> $f_{1}=O(g_{1}){\text{ and }}f_{2}=O(g_{2})\,\Rightarrow f_{1}+f_{2}=O(max(g_{1},g_{2}))$ </mn></mrow></msub><mo> $f_{1}=O(g_{1}){\text{ and }}f_{2}=O(g_{2})\,\Rightarrow f_{1}+f_{2}=O(max(g_{1},g_{2}))$ </mo><mi> $f_{1}=O(g_{1}){\text{ and }}f_{2}=O(g_{2})\,\Rightarrow f_{1}+f_{2}=O(max(g_{1},g_{2}))$ </mi><mo stretchy="false"> $f_{1}=O(g_{1}){\text{ and }}f_{2}=O(g_{2})\,\Rightarrow f_{1}+f_{2}=O(max(g_{1},g_{2}))$ </mo><msub><mi> $f_{1}=O(g_{1}){\text{ and }}f_{2}=O(g_{2})\,\Rightarrow f_{1}+f_{2}=O(max(g_{1},g_{2}))$ </mi><mrow class="MJX-TeXAtom-ORD"><mn> $f_{1}=O(g_{1}){\text{ and }}f_{2}=O(g_{2})\,\Rightarrow f_{1}+f_{2}=O(max(g_{1},g_{2}))$ </mn></mrow></msub><mo stretchy="false"> $f_{1}=O(g_{1}){\text{ and }}f_{2}=O(g_{2})\,\Rightarrow f_{1}+f_{2}=O(max(g_{1},g_{2}))$ </mo><mo stretchy="false"> $f_{1}=O(g_{1}){\text{ and }}f_{2}=O(g_{2})\,\Rightarrow f_{1}+f_{2}=O(max(g_{1},g_{2}))$ </mo><msub><mi> $f_{1}=O(g_{1}){\text{ and }}f_{2}=O(g_{2})\,\Rightarrow f_{1}+f_{2}=O(max(g_{1},g_{2}))$ </mi><mrow class="MJX-TeXAtom-ORD"><mn> $f_{1}=O(g_{1}){\text{ and }}f_{2}=O(g_{2})\,\Rightarrow f_{1}+f_{2}=O(max(g_{1},g_{2}))$ </mn></mrow></msub><mo> $f_{1}=O(g_{1}){\text{ and }}f_{2}=O(g_{2})\,\Rightarrow f_{1}+f_{2}=O(max(g_{1},g_{2}))$ </mo><msub><mi> $f_{1}=O(g_{1}){\text{ and }}f_{2}=O(g_{2})\,\Rightarrow f_{1}+f_{2}=O(max(g_{1},g_{2}))$ </mi><mrow class="MJX-TeXAtom-ORD"><mn> $f_{1}=O(g_{1}){\text{ and }}f_{2}=O(g_{2})\,\Rightarrow f_{1}+f_{2}=O(max(g_{1},g_{2}))$ </mn></mrow></msub><mo> $f_{1}=O(g_{1}){\text{ and }}f_{2}=O(g_{2})\,\Rightarrow f_{1}+f_{2}=O(max(g_{1},g_{2}))$ </mo><mi> $f_{1}=O(g_{1}){\text{ and }}f_{2}=O(g_{2})\,\Rightarrow f_{1}+f_{2}=O(max(g_{1},g_{2}))$ </mi><mo stretchy="false"> $f_{1}=O(g_{1}){\text{ and }}f_{2}=O(g_{2})\,\Rightarrow f_{1}+f_{2}=O(max(g_{1},g_{2}))$ </mo><mi> $f_{1}=O(g_{1}){\text{ and }}f_{2}=O(g_{2})\,\Rightarrow f_{1}+f_{2}=O(max(g_{1},g_{2}))$ </mi><mi> $f_{1}=O(g_{1}){\text{ and }}f_{2}=O(g_{2})\,\Rightarrow f_{1}+f_{2}=O(max(g_{1},g_{2}))$ </mi><mi> $f_{1}=O(g_{1}){\text{ and }}f_{2}=O(g_{2})\,\Rightarrow f_{1}+f_{2}=O(max(g_{1},g_{2}))$ </mi><mo stretchy="false"> $f_{1}=O(g_{1}){\text{ and }}f_{2}=O(g_{2})\,\Rightarrow f_{1}+f_{2}=O(max(g_{1},g_{2}))$ </mo><msub><mi> $f_{1}=O(g_{1}){\text{ and }}f_{2}=O(g_{2})\,\Rightarrow f_{1}+f_{2}=O(max(g_{1},g_{2}))$ </mi><mrow class="MJX-TeXAtom-ORD"><mn> $f_{1}=O(g_{1}){\text{ and }}f_{2}=O(g_{2})\,\Rightarrow f_{1}+f_{2}=O(max(g_{1},g_{2}))$ </mn></mrow></msub><mo> $f_{1}=O(g_{1}){\text{ and }}f_{2}=O(g_{2})\,\Rightarrow f_{1}+f_{2}=O(max(g_{1},g_{2}))$ </mo><msub><mi> $f_{1}=O(g_{1}){\text{ and }}f_{2}=O(g_{2})\,\Rightarrow f_{1}+f_{2}=O(max(g_{1},g_{2}))$ </mi><mrow class="MJX-TeXAtom-ORD"><mn> $f_{1}=O(g_{1}){\text{ and }}f_{2}=O(g_{2})\,\Rightarrow f_{1}+f_{2}=O(max(g_{1},g_{2}))$ </mn></mrow></msub><mo stretchy="false"> $f_{1}=O(g_{1}){\text{ and }}f_{2}=O(g_{2})\,\Rightarrow f_{1}+f_{2}=O(max(g_{1},g_{2}))$ </mo><mo stretchy="false"> $f_{1}=O(g_{1}){\text{ and }}f_{2}=O(g_{2})\,\Rightarrow f_{1}+f_{2}=O(max(g_{1},g_{2}))$ </mo></mstyle></mrow> </math>$f_{1}=O(g_{1}){\text{ and }}f_{2}=O(g_{2})\,\Rightarrow f_{1}+f_{2}=O(max(g_{1},g_{2}))$ $f_{1}=O(g_{1}){\text{ and }}f_{2}=O(g_{2})\,\Rightarrow f_{1}+f_{2}=O(max(g_{1},g_{2}))$ </img>

Asta implică Nu s-a putut interpreta (eroare de sintaxă): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><msub><mi> <math> f_1 = O(g) \text{ and } f_2 = O(g) \Rightarrow f_1+f_2 \in O(g) } </mi><mrow class="MJX-TeXAtom-ORD"><mn> $f_{1}=O(g){\text{ and }}f_{2}=O(g)\Rightarrow f_{1}+f_{2}\in O(g)$ </mn></mrow></msub><mo> $f_{1}=O(g){\text{ and }}f_{2}=O(g)\Rightarrow f_{1}+f_{2}\in O(g)$ </mo><mi> $f_{1}=O(g){\text{ and }}f_{2}=O(g)\Rightarrow f_{1}+f_{2}\in O(g)$ </mi><mo stretchy="false"> $f_{1}=O(g){\text{ and }}f_{2}=O(g)\Rightarrow f_{1}+f_{2}\in O(g)$ </mo><mi> $f_{1}=O(g){\text{ and }}f_{2}=O(g)\Rightarrow f_{1}+f_{2}\in O(g)$ </mi><mo stretchy="false"> $f_{1}=O(g){\text{ and }}f_{2}=O(g)\Rightarrow f_{1}+f_{2}\in O(g)$ </mo><mrow class="MJX-TeXAtom-ORD"><mtext> $f_{1}=O(g){\text{ and }}f_{2}=O(g)\Rightarrow f_{1}+f_{2}\in O(g)$ </mtext></mrow><msub><mi> $f_{1}=O(g){\text{ and }}f_{2}=O(g)\Rightarrow f_{1}+f_{2}\in O(g)$ </mi><mrow class="MJX-TeXAtom-ORD"><mn> $f_{1}=O(g){\text{ and }}f_{2}=O(g)\Rightarrow f_{1}+f_{2}\in O(g)$ </mn></mrow></msub><mo> $f_{1}=O(g){\text{ and }}f_{2}=O(g)\Rightarrow f_{1}+f_{2}\in O(g)$ </mo><mi> $f_{1}=O(g){\text{ and }}f_{2}=O(g)\Rightarrow f_{1}+f_{2}\in O(g)$ </mi><mo stretchy="false"> $f_{1}=O(g){\text{ and }}f_{2}=O(g)\Rightarrow f_{1}+f_{2}\in O(g)$ </mo><mi> $f_{1}=O(g){\text{ and }}f_{2}=O(g)\Rightarrow f_{1}+f_{2}\in O(g)$ </mi><mo stretchy="false"> $f_{1}=O(g){\text{ and }}f_{2}=O(g)\Rightarrow f_{1}+f_{2}\in O(g)$ </mo><mo stretchy="false"> $f_{1}=O(g){\text{ and }}f_{2}=O(g)\Rightarrow f_{1}+f_{2}\in O(g)$ </mo><msub><mi> $f_{1}=O(g){\text{ and }}f_{2}=O(g)\Rightarrow f_{1}+f_{2}\in O(g)$ </mi><mrow class="MJX-TeXAtom-ORD"><mn> $f_{1}=O(g){\text{ and }}f_{2}=O(g)\Rightarrow f_{1}+f_{2}\in O(g)$ </mn></mrow></msub><mo> $f_{1}=O(g){\text{ and }}f_{2}=O(g)\Rightarrow f_{1}+f_{2}\in O(g)$ </mo><msub><mi> $f_{1}=O(g){\text{ and }}f_{2}=O(g)\Rightarrow f_{1}+f_{2}\in O(g)$ </mi><mrow class="MJX-TeXAtom-ORD"><mn> $f_{1}=O(g){\text{ and }}f_{2}=O(g)\Rightarrow f_{1}+f_{2}\in O(g)$ </mn></mrow></msub><mo> $f_{1}=O(g){\text{ and }}f_{2}=O(g)\Rightarrow f_{1}+f_{2}\in O(g)$ </mo><mi> $f_{1}=O(g){\text{ and }}f_{2}=O(g)\Rightarrow f_{1}+f_{2}\in O(g)$ </mi><mo stretchy="false"> $f_{1}=O(g){\text{ and }}f_{2}=O(g)\Rightarrow f_{1}+f_{2}\in O(g)$ </mo><mi> $f_{1}=O(g){\text{ and }}f_{2}=O(g)\Rightarrow f_{1}+f_{2}\in O(g)$ </mi><mo stretchy="false"> $f_{1}=O(g){\text{ and }}f_{2}=O(g)\Rightarrow f_{1}+f_{2}\in O(g)$ </mo></mstyle></mrow> </math>$f_{1}=O(g){\text{ and }}f_{2}=O(g)\Rightarrow f_{1}+f_{2}\in O(g)$ $f_{1}=O(g){\text{ and }}f_{2}=O(g)\Rightarrow f_{1}+f_{2}\in O(g)$ </img> , ceea ce înseamnă că Nu s-a putut interpreta (eroare de sintaxă): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mi> <math>O(g)} </mi><mo stretchy="false"> $O(g)$ </mo><mi> $O(g)$ </mi><mo stretchy="false"> $O(g)$ </mo></mstyle></mrow> </math>$O(g)$ $O(g)$ </img> este un con convex .

Înmulțirea cu o constantă

Fie k o constantă. Atunci:

Nu s-a putut interpreta (eroare de sintaxă): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mi> <math>\ O(|k| g) = O(g)} </mi><mo stretchy="false"> $\ O(|k|g)=O(g)$ </mo><mrow class="MJX-TeXAtom-ORD"><mo stretchy="false"> $\ O(|k|g)=O(g)$ </mo></mrow><mi> $\ O(|k|g)=O(g)$ </mi><mrow class="MJX-TeXAtom-ORD"><mo stretchy="false"> $\ O(|k|g)=O(g)$ </mo></mrow><mi> $\ O(|k|g)=O(g)$ </mi><mo stretchy="false"> $\ O(|k|g)=O(g)$ </mo><mo> $\ O(|k|g)=O(g)$ </mo><mi> $\ O(|k|g)=O(g)$ </mi><mo stretchy="false"> $\ O(|k|g)=O(g)$ </mo><mi> $\ O(|k|g)=O(g)$ </mi><mo stretchy="false"> $\ O(|k|g)=O(g)$ </mo></mstyle></mrow> </math>$\ O(|k|g)=O(g)$ $\ O(|k|g)=O(g)$ </img> dacă k este nenul.

<mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mi> $f=O(g)\Rightarrow kf=O(g).$ </mi><mo> $f=O(g)\Rightarrow kf=O(g).$ </mo><mi> $f=O(g)\Rightarrow kf=O(g).$ </mi><mo stretchy="false"> $f=O(g)\Rightarrow kf=O(g).$ </mo><mi> $f=O(g)\Rightarrow kf=O(g).$ </mi><mo stretchy="false"> $f=O(g)\Rightarrow kf=O(g).$ </mo><mo stretchy="false"> $f=O(g)\Rightarrow kf=O(g).$ </mo><mi> $f=O(g)\Rightarrow kf=O(g).$ </mi><mi> $f=O(g)\Rightarrow kf=O(g).$ </mi><mo> $f=O(g)\Rightarrow kf=O(g).$ </mo><mi> $f=O(g)\Rightarrow kf=O(g).$ </mi><mo stretchy="false"> $f=O(g)\Rightarrow kf=O(g).$ </mo><mi> $f=O(g)\Rightarrow kf=O(g).$ </mi><mo stretchy="false"> $f=O(g)\Rightarrow kf=O(g).$ </mo><mo> $f=O(g)\Rightarrow kf=O(g).$ </mo></mstyle></mrow> $f=O(g)\Rightarrow kf=O(g).$ ${\displaystyle }$$f=O(g)\Rightarrow kf=O(g).$ $f=O(g)\Rightarrow kf=O(g).$ </img>

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ă f și g sunt două funcții definite pe o anumită submulțime a lui $\mathbb {R} ^{n}$ </img> . Se spune că

Nu s-a putut interpreta (eroare de sintaxă): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mi> <math>f(\vec{x})\text{ is }O(g(\vec{x}))\text{ as }\vec{x}\to\infty} </mi><mo stretchy="false"> $f({\vec {x}}){\text{ is }}O(g({\vec {x}})){\text{ as }}{\vec {x}}\to \infty$ </mo><mrow class="MJX-TeXAtom-ORD"><mrow class="MJX-TeXAtom-ORD"><mover><mi> $f({\vec {x}}){\text{ is }}O(g({\vec {x}})){\text{ as }}{\vec {x}}\to \infty$ </mi><mo stretchy="false"> $f({\vec {x}}){\text{ is }}O(g({\vec {x}})){\text{ as }}{\vec {x}}\to \infty$ </mo></mover></mrow></mrow><mo stretchy="false"> $f({\vec {x}}){\text{ is }}O(g({\vec {x}})){\text{ as }}{\vec {x}}\to \infty$ </mo><mrow class="MJX-TeXAtom-ORD"><mtext> $f({\vec {x}}){\text{ is }}O(g({\vec {x}})){\text{ as }}{\vec {x}}\to \infty$ </mtext></mrow><mi> $f({\vec {x}}){\text{ is }}O(g({\vec {x}})){\text{ as }}{\vec {x}}\to \infty$ </mi><mo stretchy="false"> $f({\vec {x}}){\text{ is }}O(g({\vec {x}})){\text{ as }}{\vec {x}}\to \infty$ </mo><mi> $f({\vec {x}}){\text{ is }}O(g({\vec {x}})){\text{ as }}{\vec {x}}\to \infty$ </mi><mo stretchy="false"> $f({\vec {x}}){\text{ is }}O(g({\vec {x}})){\text{ as }}{\vec {x}}\to \infty$ </mo><mrow class="MJX-TeXAtom-ORD"><mrow class="MJX-TeXAtom-ORD"><mover><mi> $f({\vec {x}}){\text{ is }}O(g({\vec {x}})){\text{ as }}{\vec {x}}\to \infty$ </mi><mo stretchy="false"> $f({\vec {x}}){\text{ is }}O(g({\vec {x}})){\text{ as }}{\vec {x}}\to \infty$ </mo></mover></mrow></mrow><mo stretchy="false"> $f({\vec {x}}){\text{ is }}O(g({\vec {x}})){\text{ as }}{\vec {x}}\to \infty$ </mo><mo stretchy="false"> $f({\vec {x}}){\text{ is }}O(g({\vec {x}})){\text{ as }}{\vec {x}}\to \infty$ </mo><mrow class="MJX-TeXAtom-ORD"><mtext> $f({\vec {x}}){\text{ is }}O(g({\vec {x}})){\text{ as }}{\vec {x}}\to \infty$ </mtext></mrow><mrow class="MJX-TeXAtom-ORD"><mrow class="MJX-TeXAtom-ORD"><mover><mi> $f({\vec {x}}){\text{ is }}O(g({\vec {x}})){\text{ as }}{\vec {x}}\to \infty$ </mi><mo stretchy="false"> $f({\vec {x}}){\text{ is }}O(g({\vec {x}})){\text{ as }}{\vec {x}}\to \infty$ </mo></mover></mrow></mrow><mo stretchy="false"> $f({\vec {x}}){\text{ is }}O(g({\vec {x}})){\text{ as }}{\vec {x}}\to \infty$ </mo><mi mathvariant="normal"> $f({\vec {x}}){\text{ is }}O(g({\vec {x}})){\text{ as }}{\vec {x}}\to \infty$ </mi></mstyle></mrow> </math>$f({\vec {x}}){\text{ is }}O(g({\vec {x}})){\text{ as }}{\vec {x}}\to \infty$ $f({\vec {x}}){\text{ is }}O(g({\vec {x}})){\text{ as }}{\vec {x}}\to \infty$ </img>

dacă și numai dacă

<mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mi mathvariant="normal"> $\exists M\,\exists C>0{\text{ such that for all }}{\vec {x}}{\text{ with }}x_{i}\geq M{\text{ for some }}i,|f({\vec {x}})|\leq C|g({\vec {x}})|.$ </mi><mi> $\exists M\,\exists C>0{\text{ such that for all }}{\vec {x}}{\text{ with }}x_{i}\geq M{\text{ for some }}i,|f({\vec {x}})|\leq C|g({\vec {x}})|.$ </mi><mi mathvariant="normal"> $\exists M\,\exists C>0{\text{ such that for all }}{\vec {x}}{\text{ with }}x_{i}\geq M{\text{ for some }}i,|f({\vec {x}})|\leq C|g({\vec {x}})|.$ </mi><mi> $\exists M\,\exists C>0{\text{ such that for all }}{\vec {x}}{\text{ with }}x_{i}\geq M{\text{ for some }}i,|f({\vec {x}})|\leq C|g({\vec {x}})|.$ </mi><mo> $\exists M\,\exists C>0{\text{ such that for all }}{\vec {x}}{\text{ with }}x_{i}\geq M{\text{ for some }}i,|f({\vec {x}})|\leq C|g({\vec {x}})|.$ </mo><mn> $\exists M\,\exists C>0{\text{ such that for all }}{\vec {x}}{\text{ with }}x_{i}\geq M{\text{ for some }}i,|f({\vec {x}})|\leq C|g({\vec {x}})|.$ </mn><mrow class="MJX-TeXAtom-ORD"><mtext> $\exists M\,\exists C>0{\text{ such that for all }}{\vec {x}}{\text{ with }}x_{i}\geq M{\text{ for some }}i,|f({\vec {x}})|\leq C|g({\vec {x}})|.$ </mtext></mrow><mrow class="MJX-TeXAtom-ORD"><mrow class="MJX-TeXAtom-ORD"><mover><mi> $\exists M\,\exists C>0{\text{ such that for all }}{\vec {x}}{\text{ with }}x_{i}\geq M{\text{ for some }}i,|f({\vec {x}})|\leq C|g({\vec {x}})|.$ </mi><mo stretchy="false"> $\exists M\,\exists C>0{\text{ such that for all }}{\vec {x}}{\text{ with }}x_{i}\geq M{\text{ for some }}i,|f({\vec {x}})|\leq C|g({\vec {x}})|.$ </mo></mover></mrow></mrow><mrow class="MJX-TeXAtom-ORD"><mtext> $\exists M\,\exists C>0{\text{ such that for all }}{\vec {x}}{\text{ with }}x_{i}\geq M{\text{ for some }}i,|f({\vec {x}})|\leq C|g({\vec {x}})|.$ </mtext></mrow><msub><mi> $\exists M\,\exists C>0{\text{ such that for all }}{\vec {x}}{\text{ with }}x_{i}\geq M{\text{ for some }}i,|f({\vec {x}})|\leq C|g({\vec {x}})|.$ </mi><mrow class="MJX-TeXAtom-ORD"><mi> $\exists M\,\exists C>0{\text{ such that for all }}{\vec {x}}{\text{ with }}x_{i}\geq M{\text{ for some }}i,|f({\vec {x}})|\leq C|g({\vec {x}})|.$ </mi></mrow></msub><mo> $\exists M\,\exists C>0{\text{ such that for all }}{\vec {x}}{\text{ with }}x_{i}\geq M{\text{ for some }}i,|f({\vec {x}})|\leq C|g({\vec {x}})|.$ </mo><mi> $\exists M\,\exists C>0{\text{ such that for all }}{\vec {x}}{\text{ with }}x_{i}\geq M{\text{ for some }}i,|f({\vec {x}})|\leq C|g({\vec {x}})|.$ </mi><mrow class="MJX-TeXAtom-ORD"><mtext> $\exists M\,\exists C>0{\text{ such that for all }}{\vec {x}}{\text{ with }}x_{i}\geq M{\text{ for some }}i,|f({\vec {x}})|\leq C|g({\vec {x}})|.$ </mtext></mrow><mi> $\exists M\,\exists C>0{\text{ such that for all }}{\vec {x}}{\text{ with }}x_{i}\geq M{\text{ for some }}i,|f({\vec {x}})|\leq C|g({\vec {x}})|.$ </mi><mo> $\exists M\,\exists C>0{\text{ such that for all }}{\vec {x}}{\text{ with }}x_{i}\geq M{\text{ for some }}i,|f({\vec {x}})|\leq C|g({\vec {x}})|.$ </mo><mrow class="MJX-TeXAtom-ORD"><mo stretchy="false"> $\exists M\,\exists C>0{\text{ such that for all }}{\vec {x}}{\text{ with }}x_{i}\geq M{\text{ for some }}i,|f({\vec {x}})|\leq C|g({\vec {x}})|.$ </mo></mrow><mi> $\exists M\,\exists C>0{\text{ such that for all }}{\vec {x}}{\text{ with }}x_{i}\geq M{\text{ for some }}i,|f({\vec {x}})|\leq C|g({\vec {x}})|.$ </mi><mo stretchy="false"> $\exists M\,\exists C>0{\text{ such that for all }}{\vec {x}}{\text{ with }}x_{i}\geq M{\text{ for some }}i,|f({\vec {x}})|\leq C|g({\vec {x}})|.$ </mo><mrow class="MJX-TeXAtom-ORD"><mrow class="MJX-TeXAtom-ORD"><mover><mi> $\exists M\,\exists C>0{\text{ such that for all }}{\vec {x}}{\text{ with }}x_{i}\geq M{\text{ for some }}i,|f({\vec {x}})|\leq C|g({\vec {x}})|.$ </mi><mo stretchy="false"> $\exists M\,\exists C>0{\text{ such that for all }}{\vec {x}}{\text{ with }}x_{i}\geq M{\text{ for some }}i,|f({\vec {x}})|\leq C|g({\vec {x}})|.$ </mo></mover></mrow></mrow><mo stretchy="false"> $\exists M\,\exists C>0{\text{ such that for all }}{\vec {x}}{\text{ with }}x_{i}\geq M{\text{ for some }}i,|f({\vec {x}})|\leq C|g({\vec {x}})|.$ </mo><mrow class="MJX-TeXAtom-ORD"><mo stretchy="false"> $\exists M\,\exists C>0{\text{ such that for all }}{\vec {x}}{\text{ with }}x_{i}\geq M{\text{ for some }}i,|f({\vec {x}})|\leq C|g({\vec {x}})|.$ </mo></mrow><mo> $\exists M\,\exists C>0{\text{ such that for all }}{\vec {x}}{\text{ with }}x_{i}\geq M{\text{ for some }}i,|f({\vec {x}})|\leq C|g({\vec {x}})|.$ </mo><mi> $\exists M\,\exists C>0{\text{ such that for all }}{\vec {x}}{\text{ with }}x_{i}\geq M{\text{ for some }}i,|f({\vec {x}})|\leq C|g({\vec {x}})|.$ </mi><mrow class="MJX-TeXAtom-ORD"><mo stretchy="false"> $\exists M\,\exists C>0{\text{ such that for all }}{\vec {x}}{\text{ with }}x_{i}\geq M{\text{ for some }}i,|f({\vec {x}})|\leq C|g({\vec {x}})|.$ </mo></mrow><mi> $\exists M\,\exists C>0{\text{ such that for all }}{\vec {x}}{\text{ with }}x_{i}\geq M{\text{ for some }}i,|f({\vec {x}})|\leq C|g({\vec {x}})|.$ </mi><mo stretchy="false"> $\exists M\,\exists C>0{\text{ such that for all }}{\vec {x}}{\text{ with }}x_{i}\geq M{\text{ for some }}i,|f({\vec {x}})|\leq C|g({\vec {x}})|.$ </mo><mrow class="MJX-TeXAtom-ORD"><mrow class="MJX-TeXAtom-ORD"><mover><mi> $\exists M\,\exists C>0{\text{ such that for all }}{\vec {x}}{\text{ with }}x_{i}\geq M{\text{ for some }}i,|f({\vec {x}})|\leq C|g({\vec {x}})|.$ </mi><mo stretchy="false"> $\exists M\,\exists C>0{\text{ such that for all }}{\vec {x}}{\text{ with }}x_{i}\geq M{\text{ for some }}i,|f({\vec {x}})|\leq C|g({\vec {x}})|.$ </mo></mover></mrow></mrow><mo stretchy="false"> $\exists M\,\exists C>0{\text{ such that for all }}{\vec {x}}{\text{ with }}x_{i}\geq M{\text{ for some }}i,|f({\vec {x}})|\leq C|g({\vec {x}})|.$ </mo><mrow class="MJX-TeXAtom-ORD"><mo stretchy="false"> $\exists M\,\exists C>0{\text{ such that for all }}{\vec {x}}{\text{ with }}x_{i}\geq M{\text{ for some }}i,|f({\vec {x}})|\leq C|g({\vec {x}})|.$ </mo></mrow><mo> $\exists M\,\exists C>0{\text{ such that for all }}{\vec {x}}{\text{ with }}x_{i}\geq M{\text{ for some }}i,|f({\vec {x}})|\leq C|g({\vec {x}})|.$ </mo></mstyle></mrow> $\exists M\,\exists C>0{\text{ such that for all }}{\vec {x}}{\text{ with }}x_{i}\geq M{\text{ for some }}i,|f({\vec {x}})|\leq C|g({\vec {x}})|.$ ${\displaystyle }$$\exists M\,\exists C>0{\text{ such that for all }}{\vec {x}}{\text{ with }}x_{i}\geq M{\text{ for some }}i,|f({\vec {x}})|\leq C|g({\vec {x}})|.$ $\exists M\,\exists C>0{\text{ such that for all }}{\vec {x}}{\text{ with }}x_{i}\geq M{\text{ for some }}i,|f({\vec {x}})|\leq C|g({\vec {x}})|.$ </img>

În mod echivalent, condiția Nu s-a putut interpreta (eroare de sintaxă): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><msub><mi> <math>x_i \geq M} </mi><mrow class="MJX-TeXAtom-ORD"><mi> $x_{i}\geq M$ </mi></mrow></msub><mo> $x_{i}\geq M$ </mo><mi> $x_{i}\geq M$ </mi></mstyle></mrow> </math>$x_{i}\geq M$ $x_{i}\geq M$ </img> pentru unii Nu s-a putut interpreta (eroare de sintaxă): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mi> <math>i} </mi></mstyle></mrow> </math>$i$ $i$ </img> poate fi înlocuită cu condiția Nu s-a putut interpreta (eroare de sintaxă): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mo fence="false" stretchy="false"> <math>\|\vec{x}\|_{\infty} \ge M} </mo><mrow class="MJX-TeXAtom-ORD"><mrow class="MJX-TeXAtom-ORD"><mover><mi> $\|{\vec {x}}\|_{\infty }\geq M$ </mi><mo stretchy="false"> $\|{\vec {x}}\|_{\infty }\geq M$ </mo></mover></mrow></mrow><msub><mo fence="false" stretchy="false"> $\|{\vec {x}}\|_{\infty }\geq M$ </mo><mrow class="MJX-TeXAtom-ORD"><mi mathvariant="normal"> $\|{\vec {x}}\|_{\infty }\geq M$ </mi></mrow></msub><mo> $\|{\vec {x}}\|_{\infty }\geq M$ </mo><mi> $\|{\vec {x}}\|_{\infty }\geq M$ </mi></mstyle></mrow> </math>$\|{\vec {x}}\|_{\infty }\geq M$ $\|{\vec {x}}\|_{\infty }\geq M$ </img> , unde cu Nu s-a putut interpreta (eroare de sintaxă): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mo fence="false" stretchy="false"> <math>\|\vec{x}\|_{\infty}} </mo><mrow class="MJX-TeXAtom-ORD"><mrow class="MJX-TeXAtom-ORD"><mover><mi> $\|{\vec {x}}\|_{\infty }$ </mi><mo stretchy="false"> $\|{\vec {x}}\|_{\infty }$ </mo></mover></mrow></mrow><msub><mo fence="false" stretchy="false"> $\|{\vec {x}}\|_{\infty }$ </mo><mrow class="MJX-TeXAtom-ORD"><mi mathvariant="normal"> $\|{\vec {x}}\|_{\infty }$ </mi></mrow></msub></mstyle></mrow> </math>$\|{\vec {x}}\|_{\infty }$ $\|{\vec {x}}\|_{\infty }$ </img> se notează norma Cebîșev. De exemplu, afirmația

Nu s-a putut interpreta (eroare de sintaxă): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mi> <math>f(n,m) = n^2 + m^3 + O(n+m) \text{ as } n,m\to\infty} </mi><mo stretchy="false"> $f(n,m)=n^{2}+m^{3}+O(n+m){\text{ as }}n,m\to \infty$ </mo><mi> $f(n,m)=n^{2}+m^{3}+O(n+m){\text{ as }}n,m\to \infty$ </mi><mo> $f(n,m)=n^{2}+m^{3}+O(n+m){\text{ as }}n,m\to \infty$ </mo><mi> $f(n,m)=n^{2}+m^{3}+O(n+m){\text{ as }}n,m\to \infty$ </mi><mo stretchy="false"> $f(n,m)=n^{2}+m^{3}+O(n+m){\text{ as }}n,m\to \infty$ </mo><mo> $f(n,m)=n^{2}+m^{3}+O(n+m){\text{ as }}n,m\to \infty$ </mo><msup><mi> $f(n,m)=n^{2}+m^{3}+O(n+m){\text{ as }}n,m\to \infty$ </mi><mrow class="MJX-TeXAtom-ORD"><mn> $f(n,m)=n^{2}+m^{3}+O(n+m){\text{ as }}n,m\to \infty$ </mn></mrow></msup><mo> $f(n,m)=n^{2}+m^{3}+O(n+m){\text{ as }}n,m\to \infty$ </mo><msup><mi> $f(n,m)=n^{2}+m^{3}+O(n+m){\text{ as }}n,m\to \infty$ </mi><mrow class="MJX-TeXAtom-ORD"><mn> $f(n,m)=n^{2}+m^{3}+O(n+m){\text{ as }}n,m\to \infty$ </mn></mrow></msup><mo> $f(n,m)=n^{2}+m^{3}+O(n+m){\text{ as }}n,m\to \infty$ </mo><mi> $f(n,m)=n^{2}+m^{3}+O(n+m){\text{ as }}n,m\to \infty$ </mi><mo stretchy="false"> $f(n,m)=n^{2}+m^{3}+O(n+m){\text{ as }}n,m\to \infty$ </mo><mi> $f(n,m)=n^{2}+m^{3}+O(n+m){\text{ as }}n,m\to \infty$ </mi><mo> $f(n,m)=n^{2}+m^{3}+O(n+m){\text{ as }}n,m\to \infty$ </mo><mi> $f(n,m)=n^{2}+m^{3}+O(n+m){\text{ as }}n,m\to \infty$ </mi><mo stretchy="false"> $f(n,m)=n^{2}+m^{3}+O(n+m){\text{ as }}n,m\to \infty$ </mo><mrow class="MJX-TeXAtom-ORD"><mtext> $f(n,m)=n^{2}+m^{3}+O(n+m){\text{ as }}n,m\to \infty$ </mtext></mrow><mi> $f(n,m)=n^{2}+m^{3}+O(n+m){\text{ as }}n,m\to \infty$ </mi><mo> $f(n,m)=n^{2}+m^{3}+O(n+m){\text{ as }}n,m\to \infty$ </mo><mi> $f(n,m)=n^{2}+m^{3}+O(n+m){\text{ as }}n,m\to \infty$ </mi><mo stretchy="false"> $f(n,m)=n^{2}+m^{3}+O(n+m){\text{ as }}n,m\to \infty$ </mo><mi mathvariant="normal"> $f(n,m)=n^{2}+m^{3}+O(n+m){\text{ as }}n,m\to \infty$ </mi></mstyle></mrow> </math>$f(n,m)=n^{2}+m^{3}+O(n+m){\text{ as }}n,m\to \infty$ $f(n,m)=n^{2}+m^{3}+O(n+m){\text{ as }}n,m\to \infty$ </img>

spune că există constantele C și M astfel încât

Nu s-a putut interpreta (eroare de sintaxă): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mi mathvariant="normal"> <math>\forall \|(n, m)\|_{\infty} \geq M: |g(n,m)| \le C|n+m|,} </mi><mo fence="false" stretchy="false"> $\forall \|(n,m)\|_{\infty }\geq M:|g(n,m)|\leq C|n+m|,$ </mo><mo stretchy="false"> $\forall \|(n,m)\|_{\infty }\geq M:|g(n,m)|\leq C|n+m|,$ </mo><mi> $\forall \|(n,m)\|_{\infty }\geq M:|g(n,m)|\leq C|n+m|,$ </mi><mo> $\forall \|(n,m)\|_{\infty }\geq M:|g(n,m)|\leq C|n+m|,$ </mo><mi> $\forall \|(n,m)\|_{\infty }\geq M:|g(n,m)|\leq C|n+m|,$ </mi><mo stretchy="false"> $\forall \|(n,m)\|_{\infty }\geq M:|g(n,m)|\leq C|n+m|,$ </mo><msub><mo fence="false" stretchy="false"> $\forall \|(n,m)\|_{\infty }\geq M:|g(n,m)|\leq C|n+m|,$ </mo><mrow class="MJX-TeXAtom-ORD"><mi mathvariant="normal"> $\forall \|(n,m)\|_{\infty }\geq M:|g(n,m)|\leq C|n+m|,$ </mi></mrow></msub><mo> $\forall \|(n,m)\|_{\infty }\geq M:|g(n,m)|\leq C|n+m|,$ </mo><mi> $\forall \|(n,m)\|_{\infty }\geq M:|g(n,m)|\leq C|n+m|,$ </mi><mo> $\forall \|(n,m)\|_{\infty }\geq M:|g(n,m)|\leq C|n+m|,$ </mo><mrow class="MJX-TeXAtom-ORD"><mo stretchy="false"> $\forall \|(n,m)\|_{\infty }\geq M:|g(n,m)|\leq C|n+m|,$ </mo></mrow><mi> $\forall \|(n,m)\|_{\infty }\geq M:|g(n,m)|\leq C|n+m|,$ </mi><mo stretchy="false"> $\forall \|(n,m)\|_{\infty }\geq M:|g(n,m)|\leq C|n+m|,$ </mo><mi> $\forall \|(n,m)\|_{\infty }\geq M:|g(n,m)|\leq C|n+m|,$ </mi><mo> $\forall \|(n,m)\|_{\infty }\geq M:|g(n,m)|\leq C|n+m|,$ </mo><mi> $\forall \|(n,m)\|_{\infty }\geq M:|g(n,m)|\leq C|n+m|,$ </mi><mo stretchy="false"> $\forall \|(n,m)\|_{\infty }\geq M:|g(n,m)|\leq C|n+m|,$ </mo><mrow class="MJX-TeXAtom-ORD"><mo stretchy="false"> $\forall \|(n,m)\|_{\infty }\geq M:|g(n,m)|\leq C|n+m|,$ </mo></mrow><mo> $\forall \|(n,m)\|_{\infty }\geq M:|g(n,m)|\leq C|n+m|,$ </mo><mi> $\forall \|(n,m)\|_{\infty }\geq M:|g(n,m)|\leq C|n+m|,$ </mi><mrow class="MJX-TeXAtom-ORD"><mo stretchy="false"> $\forall \|(n,m)\|_{\infty }\geq M:|g(n,m)|\leq C|n+m|,$ </mo></mrow><mi> $\forall \|(n,m)\|_{\infty }\geq M:|g(n,m)|\leq C|n+m|,$ </mi><mo> $\forall \|(n,m)\|_{\infty }\geq M:|g(n,m)|\leq C|n+m|,$ </mo><mi> $\forall \|(n,m)\|_{\infty }\geq M:|g(n,m)|\leq C|n+m|,$ </mi><mrow class="MJX-TeXAtom-ORD"><mo stretchy="false"> $\forall \|(n,m)\|_{\infty }\geq M:|g(n,m)|\leq C|n+m|,$ </mo></mrow><mo> $\forall \|(n,m)\|_{\infty }\geq M:|g(n,m)|\leq C|n+m|,$ </mo></mstyle></mrow> </math>$\forall \|(n,m)\|_{\infty }\geq M:|g(n,m)|\leq C|n+m|,$ $\forall \|(n,m)\|_{\infty }\geq M:|g(n,m)|\leq C|n+m|,$ </img>

unde g(n, m) se definește ca

<mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mi> $f(n,m)=n^{2}+m^{3}+g(n,m).$ </mi><mo stretchy="false"> $f(n,m)=n^{2}+m^{3}+g(n,m).$ </mo><mi> $f(n,m)=n^{2}+m^{3}+g(n,m).$ </mi><mo> $f(n,m)=n^{2}+m^{3}+g(n,m).$ </mo><mi> $f(n,m)=n^{2}+m^{3}+g(n,m).$ </mi><mo stretchy="false"> $f(n,m)=n^{2}+m^{3}+g(n,m).$ </mo><mo> $f(n,m)=n^{2}+m^{3}+g(n,m).$ </mo><msup><mi> $f(n,m)=n^{2}+m^{3}+g(n,m).$ </mi><mrow class="MJX-TeXAtom-ORD"><mn> $f(n,m)=n^{2}+m^{3}+g(n,m).$ </mn></mrow></msup><mo> $f(n,m)=n^{2}+m^{3}+g(n,m).$ </mo><msup><mi> $f(n,m)=n^{2}+m^{3}+g(n,m).$ </mi><mrow class="MJX-TeXAtom-ORD"><mn> $f(n,m)=n^{2}+m^{3}+g(n,m).$ </mn></mrow></msup><mo> $f(n,m)=n^{2}+m^{3}+g(n,m).$ </mo><mi> $f(n,m)=n^{2}+m^{3}+g(n,m).$ </mi><mo stretchy="false"> $f(n,m)=n^{2}+m^{3}+g(n,m).$ </mo><mi> $f(n,m)=n^{2}+m^{3}+g(n,m).$ </mi><mo> $f(n,m)=n^{2}+m^{3}+g(n,m).$ </mo><mi> $f(n,m)=n^{2}+m^{3}+g(n,m).$ </mi><mo stretchy="false"> $f(n,m)=n^{2}+m^{3}+g(n,m).$ </mo><mo> $f(n,m)=n^{2}+m^{3}+g(n,m).$ </mo></mstyle></mrow> $f(n,m)=n^{2}+m^{3}+g(n,m).$ ${\displaystyle }$$f(n,m)=n^{2}+m^{3}+g(n,m).$ $f(n,m)=n^{2}+m^{3}+g(n,m).$ </img>

Această definiție permite ca toate coordonatele luiNu s-a putut interpreta (eroare de sintaxă): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mrow class="MJX-TeXAtom-ORD"><mrow class="MJX-TeXAtom-ORD"><mover><mi> <math>\vec{x}} </mi><mo stretchy="false"> ${\vec {x}}$ </mo></mover></mrow></mrow></mstyle></mrow> </math>${\vec {x}}$ ${\vec {x}}$ </img> să crească până la infinit. În special, afirmația

Nu s-a putut interpreta (eroare de sintaxă): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mi> <math>f(n,m) = O(n^m) \text{ as } n,m\to\infty} </mi><mo stretchy="false"> $f(n,m)=O(n^{m}){\text{ as }}n,m\to \infty$ </mo><mi> $f(n,m)=O(n^{m}){\text{ as }}n,m\to \infty$ </mi><mo> $f(n,m)=O(n^{m}){\text{ as }}n,m\to \infty$ </mo><mi> $f(n,m)=O(n^{m}){\text{ as }}n,m\to \infty$ </mi><mo stretchy="false"> $f(n,m)=O(n^{m}){\text{ as }}n,m\to \infty$ </mo><mo> $f(n,m)=O(n^{m}){\text{ as }}n,m\to \infty$ </mo><mi> $f(n,m)=O(n^{m}){\text{ as }}n,m\to \infty$ </mi><mo stretchy="false"> $f(n,m)=O(n^{m}){\text{ as }}n,m\to \infty$ </mo><msup><mi> $f(n,m)=O(n^{m}){\text{ as }}n,m\to \infty$ </mi><mrow class="MJX-TeXAtom-ORD"><mi> $f(n,m)=O(n^{m}){\text{ as }}n,m\to \infty$ </mi></mrow></msup><mo stretchy="false"> $f(n,m)=O(n^{m}){\text{ as }}n,m\to \infty$ </mo><mrow class="MJX-TeXAtom-ORD"><mtext> $f(n,m)=O(n^{m}){\text{ as }}n,m\to \infty$ </mtext></mrow><mi> $f(n,m)=O(n^{m}){\text{ as }}n,m\to \infty$ </mi><mo> $f(n,m)=O(n^{m}){\text{ as }}n,m\to \infty$ </mo><mi> $f(n,m)=O(n^{m}){\text{ as }}n,m\to \infty$ </mi><mo stretchy="false"> $f(n,m)=O(n^{m}){\text{ as }}n,m\to \infty$ </mo><mi mathvariant="normal"> $f(n,m)=O(n^{m}){\text{ as }}n,m\to \infty$ </mi></mstyle></mrow> </math>$f(n,m)=O(n^{m}){\text{ as }}n,m\to \infty$ $f(n,m)=O(n^{m}){\text{ as }}n,m\to \infty$ </img>

( de exemplu, Nu s-a putut interpreta (eroare de sintaxă): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mi mathvariant="normal"> <math>\exists C\,\exists M\,\forall n\,\forall m\dots} </mi><mi> $\exists C\,\exists M\,\forall n\,\forall m\dots$ </mi><mi mathvariant="normal"> $\exists C\,\exists M\,\forall n\,\forall m\dots$ </mi><mi> $\exists C\,\exists M\,\forall n\,\forall m\dots$ </mi><mi mathvariant="normal"> $\exists C\,\exists M\,\forall n\,\forall m\dots$ </mi><mi> $\exists C\,\exists M\,\forall n\,\forall m\dots$ </mi><mi mathvariant="normal"> $\exists C\,\exists M\,\forall n\,\forall m\dots$ </mi><mi> $\exists C\,\exists M\,\forall n\,\forall m\dots$ </mi><mo> $\exists C\,\exists M\,\forall n\,\forall m\dots$ </mo></mstyle></mrow> </math>$\exists C\,\exists M\,\forall n\,\forall m\dots$ $\exists C\,\exists M\,\forall n\,\forall m\dots$ </img> ) este destul de diferită de

Nu s-a putut interpreta (eroare de sintaxă): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mi mathvariant="normal"> <math>\forall m\colon f(n,m) = O(n^m) \text{ as } n\to\infty} </mi><mi> $\forall m\colon f(n,m)=O(n^{m}){\text{ as }}n\to \infty$ </mi><mo> $\forall m\colon f(n,m)=O(n^{m}){\text{ as }}n\to \infty$ </mo><mi> $\forall m\colon f(n,m)=O(n^{m}){\text{ as }}n\to \infty$ </mi><mo stretchy="false"> $\forall m\colon f(n,m)=O(n^{m}){\text{ as }}n\to \infty$ </mo><mi> $\forall m\colon f(n,m)=O(n^{m}){\text{ as }}n\to \infty$ </mi><mo> $\forall m\colon f(n,m)=O(n^{m}){\text{ as }}n\to \infty$ </mo><mi> $\forall m\colon f(n,m)=O(n^{m}){\text{ as }}n\to \infty$ </mi><mo stretchy="false"> $\forall m\colon f(n,m)=O(n^{m}){\text{ as }}n\to \infty$ </mo><mo> $\forall m\colon f(n,m)=O(n^{m}){\text{ as }}n\to \infty$ </mo><mi> $\forall m\colon f(n,m)=O(n^{m}){\text{ as }}n\to \infty$ </mi><mo stretchy="false"> $\forall m\colon f(n,m)=O(n^{m}){\text{ as }}n\to \infty$ </mo><msup><mi> $\forall m\colon f(n,m)=O(n^{m}){\text{ as }}n\to \infty$ </mi><mrow class="MJX-TeXAtom-ORD"><mi> $\forall m\colon f(n,m)=O(n^{m}){\text{ as }}n\to \infty$ </mi></mrow></msup><mo stretchy="false"> $\forall m\colon f(n,m)=O(n^{m}){\text{ as }}n\to \infty$ </mo><mrow class="MJX-TeXAtom-ORD"><mtext> $\forall m\colon f(n,m)=O(n^{m}){\text{ as }}n\to \infty$ </mtext></mrow><mi> $\forall m\colon f(n,m)=O(n^{m}){\text{ as }}n\to \infty$ </mi><mo stretchy="false"> $\forall m\colon f(n,m)=O(n^{m}){\text{ as }}n\to \infty$ </mo><mi mathvariant="normal"> $\forall m\colon f(n,m)=O(n^{m}){\text{ as }}n\to \infty$ </mi></mstyle></mrow> </math>$\forall m\colon f(n,m)=O(n^{m}){\text{ as }}n\to \infty$ $\forall m\colon f(n,m)=O(n^{m}){\text{ as }}n\to \infty$ </img>

( de exemplu, Nu s-a putut interpreta (eroare de sintaxă): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mi mathvariant="normal"> <math>\forall m\,\exists C\,\exists M\,\forall n\dots} </mi><mi> $\forall m\,\exists C\,\exists M\,\forall n\dots$ </mi><mi mathvariant="normal"> $\forall m\,\exists C\,\exists M\,\forall n\dots$ </mi><mi> $\forall m\,\exists C\,\exists M\,\forall n\dots$ </mi><mi mathvariant="normal"> $\forall m\,\exists C\,\exists M\,\forall n\dots$ </mi><mi> $\forall m\,\exists C\,\exists M\,\forall n\dots$ </mi><mi mathvariant="normal"> $\forall m\,\exists C\,\exists M\,\forall n\dots$ </mi><mi> $\forall m\,\exists C\,\exists M\,\forall n\dots$ </mi><mo> $\forall m\,\exists C\,\exists M\,\forall n\dots$ </mo></mstyle></mrow> </math>$\forall m\,\exists C\,\exists M\,\forall n\dots$ $\forall m\,\exists C\,\exists M\,\forall n\dots$ </img> ).

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ă Nu s-a putut interpreta (eroare de sintaxă): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mi> <math>f(n,m)=1} </mi><mo stretchy="false"> $f(n,m)=1$ </mo><mi> $f(n,m)=1$ </mi><mo> $f(n,m)=1$ </mo><mi> $f(n,m)=1$ </mi><mo stretchy="false"> $f(n,m)=1$ </mo><mo> $f(n,m)=1$ </mo><mn> $f(n,m)=1$ </mn></mstyle></mrow> </math>$f(n,m)=1$ $f(n,m)=1$ </img> și Nu s-a putut interpreta (eroare de sintaxă): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mi> <math>g(n,m)=n} </mi><mo stretchy="false"> $g(n,m)=n$ </mo><mi> $g(n,m)=n$ </mi><mo> $g(n,m)=n$ </mo><mi> $g(n,m)=n$ </mi><mo stretchy="false"> $g(n,m)=n$ </mo><mo> $g(n,m)=n$ </mo><mi> $g(n,m)=n$ </mi></mstyle></mrow> </math>$g(n,m)=n$ $g(n,m)=n$ </img> , atunci Nu s-a putut interpreta (eroare de sintaxă): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mi> <math>f(n,m)=O(g(n,m))} </mi><mo stretchy="false"> $f(n,m)=O(g(n,m))$ </mo><mi> $f(n,m)=O(g(n,m))$ </mi><mo> $f(n,m)=O(g(n,m))$ </mo><mi> $f(n,m)=O(g(n,m))$ </mi><mo stretchy="false"> $f(n,m)=O(g(n,m))$ </mo><mo> $f(n,m)=O(g(n,m))$ </mo><mi> $f(n,m)=O(g(n,m))$ </mi><mo stretchy="false"> $f(n,m)=O(g(n,m))$ </mo><mi> $f(n,m)=O(g(n,m))$ </mi><mo stretchy="false"> $f(n,m)=O(g(n,m))$ </mo><mi> $f(n,m)=O(g(n,m))$ </mi><mo> $f(n,m)=O(g(n,m))$ </mo><mi> $f(n,m)=O(g(n,m))$ </mi><mo stretchy="false"> $f(n,m)=O(g(n,m))$ </mo><mo stretchy="false"> $f(n,m)=O(g(n,m))$ </mo></mstyle></mrow> </math>$f(n,m)=O(g(n,m))$ $f(n,m)=O(g(n,m))$ </img> dacă se restrâng Nu s-a putut interpreta (eroare de sintaxă): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mi> <math>f} </mi></mstyle></mrow> </math>$f$ $f$ </img> și Nu s-a putut interpreta (eroare de sintaxă): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mi> <math>g} </mi></mstyle></mrow> </math>$g$ $g$ </img> la Nu s-a putut interpreta (eroare de sintaxă): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mo stretchy="false"> <math>[1,\infty)^2} </mo><mn> $[1,\infty )^{2}$ </mn><mo> $[1,\infty )^{2}$ </mo><mi mathvariant="normal"> $[1,\infty )^{2}$ </mi><msup><mo stretchy="false"> $[1,\infty )^{2}$ </mo><mrow class="MJX-TeXAtom-ORD"><mn> $[1,\infty )^{2}$ </mn></mrow></msup></mstyle></mrow> </math>$[1,\infty )^{2}$ $[1,\infty )^{2}$ </img> , dar nu dacă acestea sunt definite pe Nu s-a putut interpreta (eroare de sintaxă): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mo stretchy="false"> <math>[0,\infty)^2} </mo><mn> $[0,\infty )^{2}$ </mn><mo> $[0,\infty )^{2}$ </mo><mi mathvariant="normal"> $[0,\infty )^{2}$ </mi><msup><mo stretchy="false"> $[0,\infty )^{2}$ </mo><mrow class="MJX-TeXAtom-ORD"><mn> $[0,\infty )^{2}$ </mn></mrow></msup></mstyle></mrow> </math>$[0,\infty )^{2}$ $[0,\infty )^{2}$ </img> .

Aceasta nu este singura generalizare a funcțiilor Big O la funcții multivariabilă, iar în practică există o anumită inconsistență în alegerea definiției.

Chestiuni de notație

Semnul egal

Afirmația f(x) este O(g(x)), așa cum este definită mai sus, se scrie de obicei ca f(x) = O(g(x)). Unii consideră că acest lucru este un 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 de Bruijn, este adevărat că O(x) = O(x²), dar nu și că O(x²) = O(x). 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 n = n² din identitățile n = O(n²)și n² = O(n²).”

Din aceste motive, ar fi mai precis să folosim notația mulțimilor și să scriem f(x) ∈ O(g(x)), considerând O(g(x)) ca clasă a tuturor funcțiilor h(x) astfel încât | h(x) | ≤ C | g(x) | pentru o constantă C. 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.”

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 h(x) + O(f(x)) se notează colecția de funcții având creșterea h(x) plus o parte a cărei creștere este limitată la f(x). Prin urmare,

Nu s-a putut interpreta (eroare de sintaxă): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mi> <math>g(x) = h(x) + O(f(x))} </mi><mo stretchy="false"> $g(x)=h(x)+O(f(x))$ </mo><mi> $g(x)=h(x)+O(f(x))$ </mi><mo stretchy="false"> $g(x)=h(x)+O(f(x))$ </mo><mo> $g(x)=h(x)+O(f(x))$ </mo><mi> $g(x)=h(x)+O(f(x))$ </mi><mo stretchy="false"> $g(x)=h(x)+O(f(x))$ </mo><mi> $g(x)=h(x)+O(f(x))$ </mi><mo stretchy="false"> $g(x)=h(x)+O(f(x))$ </mo><mo> $g(x)=h(x)+O(f(x))$ </mo><mi> $g(x)=h(x)+O(f(x))$ </mi><mo stretchy="false"> $g(x)=h(x)+O(f(x))$ </mo><mi> $g(x)=h(x)+O(f(x))$ </mi><mo stretchy="false"> $g(x)=h(x)+O(f(x))$ </mo><mi> $g(x)=h(x)+O(f(x))$ </mi><mo stretchy="false"> $g(x)=h(x)+O(f(x))$ </mo><mo stretchy="false"> $g(x)=h(x)+O(f(x))$ </mo></mstyle></mrow> </math>$g(x)=h(x)+O(f(x))$ $g(x)=h(x)+O(f(x))$ </img>

exprimă același lucru ca și

<mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mi> $g(x)-h(x)=O(f(x))\,.$ </mi><mo stretchy="false"> $g(x)-h(x)=O(f(x))\,.$ </mo><mi> $g(x)-h(x)=O(f(x))\,.$ </mi><mo stretchy="false"> $g(x)-h(x)=O(f(x))\,.$ </mo><mo> $g(x)-h(x)=O(f(x))\,.$ </mo><mi> $g(x)-h(x)=O(f(x))\,.$ </mi><mo stretchy="false"> $g(x)-h(x)=O(f(x))\,.$ </mo><mi> $g(x)-h(x)=O(f(x))\,.$ </mi><mo stretchy="false"> $g(x)-h(x)=O(f(x))\,.$ </mo><mo> $g(x)-h(x)=O(f(x))\,.$ </mo><mi> $g(x)-h(x)=O(f(x))\,.$ </mi><mo stretchy="false"> $g(x)-h(x)=O(f(x))\,.$ </mo><mi> $g(x)-h(x)=O(f(x))\,.$ </mi><mo stretchy="false"> $g(x)-h(x)=O(f(x))\,.$ </mo><mi> $g(x)-h(x)=O(f(x))\,.$ </mi><mo stretchy="false"> $g(x)-h(x)=O(f(x))\,.$ </mo><mo stretchy="false"> $g(x)-h(x)=O(f(x))\,.$ </mo><mo> $g(x)-h(x)=O(f(x))\,.$ </mo></mstyle></mrow> $g(x)-h(x)=O(f(x))\,.$ ${\displaystyle }$$g(x)-h(x)=O(f(x))\,.$ $g(x)-h(x)=O(f(x))\,.$ </img>

Exemplu

Să presupunem că se dezvoltă un algoritm care să funcționeze pe o mulțime de n elemente. Dezvoltatorii săi sunt interesați să găsească o funcție 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 O(n²), iar după executarea subrutinei algoritmul trebuie să mai ruleze încă 55n³ + 2n + 10 pași înainte de a se termina. Astfel, complexitatea în timp a algoritmului poate fi exprimată ca T(n) = 55 n³ + O(n²). Aici termenii 2n + 10 sunt subsumați în cadrul lui O(n²) 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 Nu s-a putut interpreta (eroare de sintaxă): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mi> <math>n\to\infty} </mi><mo stretchy="false"> $n\to \infty$ </mo><mi mathvariant="normal"> $n\to \infty$ </mi></mstyle></mrow> </math>$n\to \infty$ $n\to \infty$ </img>

Nu s-a putut interpreta (eroare de sintaxă): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mo stretchy="false"> <math>(n+1)^2 = n^2 + O(n)} </mo><mi> $(n+1)^{2}=n^{2}+O(n)$ </mi><mo> $(n+1)^{2}=n^{2}+O(n)$ </mo><mn> $(n+1)^{2}=n^{2}+O(n)$ </mn><msup><mo stretchy="false"> $(n+1)^{2}=n^{2}+O(n)$ </mo><mrow class="MJX-TeXAtom-ORD"><mn> $(n+1)^{2}=n^{2}+O(n)$ </mn></mrow></msup><mo> $(n+1)^{2}=n^{2}+O(n)$ </mo><msup><mi> $(n+1)^{2}=n^{2}+O(n)$ </mi><mrow class="MJX-TeXAtom-ORD"><mn> $(n+1)^{2}=n^{2}+O(n)$ </mn></mrow></msup><mo> $(n+1)^{2}=n^{2}+O(n)$ </mo><mi> $(n+1)^{2}=n^{2}+O(n)$ </mi><mo stretchy="false"> $(n+1)^{2}=n^{2}+O(n)$ </mo><mi> $(n+1)^{2}=n^{2}+O(n)$ </mi><mo stretchy="false"> $(n+1)^{2}=n^{2}+O(n)$ </mo></mstyle></mrow> </math>$(n+1)^{2}=n^{2}+O(n)$ $(n+1)^{2}=n^{2}+O(n)$ </img>

Nu s-a putut interpreta (eroare de sintaxă): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mo stretchy="false"> <math>(n+O(n^{1/2}))(n + O(\log n))^2 = n^3 + O(n^{5/2})} </mo><mi> $(n+O(n^{1/2}))(n+O(\log n))^{2}=n^{3}+O(n^{5/2})$ </mi><mo> $(n+O(n^{1/2}))(n+O(\log n))^{2}=n^{3}+O(n^{5/2})$ </mo><mi> $(n+O(n^{1/2}))(n+O(\log n))^{2}=n^{3}+O(n^{5/2})$ </mi><mo stretchy="false"> $(n+O(n^{1/2}))(n+O(\log n))^{2}=n^{3}+O(n^{5/2})$ </mo><msup><mi> $(n+O(n^{1/2}))(n+O(\log n))^{2}=n^{3}+O(n^{5/2})$ </mi><mrow class="MJX-TeXAtom-ORD"><mn> $(n+O(n^{1/2}))(n+O(\log n))^{2}=n^{3}+O(n^{5/2})$ </mn><mrow class="MJX-TeXAtom-ORD"><mo> $(n+O(n^{1/2}))(n+O(\log n))^{2}=n^{3}+O(n^{5/2})$ </mo></mrow><mn> $(n+O(n^{1/2}))(n+O(\log n))^{2}=n^{3}+O(n^{5/2})$ </mn></mrow></msup><mo stretchy="false"> $(n+O(n^{1/2}))(n+O(\log n))^{2}=n^{3}+O(n^{5/2})$ </mo><mo stretchy="false"> $(n+O(n^{1/2}))(n+O(\log n))^{2}=n^{3}+O(n^{5/2})$ </mo><mo stretchy="false"> $(n+O(n^{1/2}))(n+O(\log n))^{2}=n^{3}+O(n^{5/2})$ </mo><mi> $(n+O(n^{1/2}))(n+O(\log n))^{2}=n^{3}+O(n^{5/2})$ </mi><mo> $(n+O(n^{1/2}))(n+O(\log n))^{2}=n^{3}+O(n^{5/2})$ </mo><mi> $(n+O(n^{1/2}))(n+O(\log n))^{2}=n^{3}+O(n^{5/2})$ </mi><mo stretchy="false"> $(n+O(n^{1/2}))(n+O(\log n))^{2}=n^{3}+O(n^{5/2})$ </mo><mi> $(n+O(n^{1/2}))(n+O(\log n))^{2}=n^{3}+O(n^{5/2})$ </mi><mo> $(n+O(n^{1/2}))(n+O(\log n))^{2}=n^{3}+O(n^{5/2})$ </mo><mi> $(n+O(n^{1/2}))(n+O(\log n))^{2}=n^{3}+O(n^{5/2})$ </mi><mo stretchy="false"> $(n+O(n^{1/2}))(n+O(\log n))^{2}=n^{3}+O(n^{5/2})$ </mo><msup><mo stretchy="false"> $(n+O(n^{1/2}))(n+O(\log n))^{2}=n^{3}+O(n^{5/2})$ </mo><mrow class="MJX-TeXAtom-ORD"><mn> $(n+O(n^{1/2}))(n+O(\log n))^{2}=n^{3}+O(n^{5/2})$ </mn></mrow></msup><mo> $(n+O(n^{1/2}))(n+O(\log n))^{2}=n^{3}+O(n^{5/2})$ </mo><msup><mi> $(n+O(n^{1/2}))(n+O(\log n))^{2}=n^{3}+O(n^{5/2})$ </mi><mrow class="MJX-TeXAtom-ORD"><mn> $(n+O(n^{1/2}))(n+O(\log n))^{2}=n^{3}+O(n^{5/2})$ </mn></mrow></msup><mo> $(n+O(n^{1/2}))(n+O(\log n))^{2}=n^{3}+O(n^{5/2})$ </mo><mi> $(n+O(n^{1/2}))(n+O(\log n))^{2}=n^{3}+O(n^{5/2})$ </mi><mo stretchy="false"> $(n+O(n^{1/2}))(n+O(\log n))^{2}=n^{3}+O(n^{5/2})$ </mo><msup><mi> $(n+O(n^{1/2}))(n+O(\log n))^{2}=n^{3}+O(n^{5/2})$ </mi><mrow class="MJX-TeXAtom-ORD"><mn> $(n+O(n^{1/2}))(n+O(\log n))^{2}=n^{3}+O(n^{5/2})$ </mn><mrow class="MJX-TeXAtom-ORD"><mo> $(n+O(n^{1/2}))(n+O(\log n))^{2}=n^{3}+O(n^{5/2})$ </mo></mrow><mn> $(n+O(n^{1/2}))(n+O(\log n))^{2}=n^{3}+O(n^{5/2})$ </mn></mrow></msup><mo stretchy="false"> $(n+O(n^{1/2}))(n+O(\log n))^{2}=n^{3}+O(n^{5/2})$ </mo></mstyle></mrow> </math>$(n+O(n^{1/2}))(n+O(\log n))^{2}=n^{3}+O(n^{5/2})$ $(n+O(n^{1/2}))(n+O(\log n))^{2}=n^{3}+O(n^{5/2})$ </img>

<mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><msup><mi> $n^{O(1)}=O(e^{n}).$ </mi><mrow class="MJX-TeXAtom-ORD"><mi> $n^{O(1)}=O(e^{n}).$ </mi><mo stretchy="false"> $n^{O(1)}=O(e^{n}).$ </mo><mn> $n^{O(1)}=O(e^{n}).$ </mn><mo stretchy="false"> $n^{O(1)}=O(e^{n}).$ </mo></mrow></msup><mo> $n^{O(1)}=O(e^{n}).$ </mo><mi> $n^{O(1)}=O(e^{n}).$ </mi><mo stretchy="false"> $n^{O(1)}=O(e^{n}).$ </mo><msup><mi> $n^{O(1)}=O(e^{n}).$ </mi><mrow class="MJX-TeXAtom-ORD"><mi> $n^{O(1)}=O(e^{n}).$ </mi></mrow></msup><mo stretchy="false"> $n^{O(1)}=O(e^{n}).$ </mo><mo> $n^{O(1)}=O(e^{n}).$ </mo></mstyle></mrow> $n^{O(1)}=O(e^{n}).$ ${\displaystyle }$$n^{O(1)}=O(e^{n}).$ $n^{O(1)}=O(e^{n}).$ </img>

Semnificația acestor afirmații este următoarea: pentru orice funcție care satisface fiecare O (...) din partea stângă, există câteva funcții care satisfac fiecare 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 f(n) = O(1), există o funcție g(n) = O(eⁿ) astfel încât n^f(n) = 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 relație simetrică. Astfel, de exemplu, n^O(1) = O(eⁿ) nu implică și afirmația falsă O(eⁿ) = n^O(1)

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 Nu s-a putut interpreta (eroare de sintaxă): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mrow class="MJX-TeXAtom-ORD"><mrow class="MJX-TeXAtom-ORD"><mi class="MJX-tex-caligraphic" mathvariant="script"> <math>\mathcal{O}} </mi></mrow></mrow></mstyle></mrow> </math>${\mathcal {O}}$ ${\mathcal {O}}$ </img> , sunt disponibile în sistemele LaTeX și în sisteme de fonturi derivate.

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, c este o constantă pozitivă și n crește fără limitări. Funcțiile cu o creștere mai lentă sunt în general enumerate mai întâi.

Notație	Nume	Exemple
$O(1)$	constantă	Determinarea dacă un număr binar este par sau impar; Calculul lui $(-1)^{n}$; Utilizarea unei tabele de căutare de dimensiuni constante
$O(\log \log n)$	dublu logaritmică	Numărul de comparații folosit pentru a găsi un element folosind căutarea prin interpolare într-un tabel sortat de valori uniform distribuite
$O(\log n)$	logaritmică	Găsirea unui element într-un tablou sortat cu căutare binară sau cu un arbore de căutare echilibrat, precum și toate operațiile pe un heap binomial
$O((\log n)^{c})$ $\scriptstyle c>1$	polilogaritmică	Ordonarea lanțurilor de matrice poate fi rezolvată în timp polilogaritmic pe o mașină cu acces aleator paralel.
$O(n^{c})$ $\scriptstyle 0<c<1$	putere fracționară	Căutarea într-un arbore k-d
$O(n)$	liniară	Găsirea unui element într-o listă neordonată sau într-un tablou neordonat; adunarea a doi întregi pe n biți prin sumatoare cu transport.
$O(n\log ^{*}n)$	n log-star n	Efectuarea de triangulații ale unui poligon simplu folosind algoritmul lui Seidel, sau algoritmul union–find. $\log ^{*}(n)={\begin{cases}0,&{\text{if }}n\leq 1\\1+\log ^{*}(\log n),&{\text{if }}n>1\end{cases}}$
$O(n\log n)=O(\log n!)$	linearitmică, logliniară, sau cvasiliniară	Efecturea unei transformări Fourier rapide; Cea mai rapidă sortare cu comparație; heapsort and merge sort
$O(n^{2})$	pătratică	Înmulțirea a două numere cu n cifre printr-un algoritm simplu; algoritmi de sortare simpli, cum ar fi bubble sort, selection sort și insertion sort; limita (în cel mai rău caz) a unor algoritmi de regulă mai rapizi, ca quicksort, Shellsort, și tree sort
$O(n^{c})$	polinomială sau algebrică	Parsarea unor gramatici cu arbori adjuncți; cuplajul maxim pentru grafuri bipartite; găsirea determinantului prin descompunere LU
$L_{n}[\alpha ,c]=e^{(c+o(1))(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }}$ $\scriptstyle 0<\alpha <1$	Notația L sausubexponențială	Factorizarea unui număr folosind ciurul pătratic sau ciurul algebric
$O(c^{n})$ $\scriptstyle c>1$	exponențtială	Găsirea soluției (exacte) a problemei comis-voiajorului folosind programare dinamică; aflarea dacă două afirmații logice sunt echivalente folosind căutarea cu forță brută
$O(n!)$	factorială	Rezolvarea problemei comis-voiajorului prin căutarea cu forță brută; generarea tuturor permutațiilor nerestricționate ale unei mulțimi parțial ordonate; găsirea determinantului prin dezvoltare Laplace; enumerarea tuturor partițiilor unei mulțimi

Afirmația Nu s-a putut interpreta (eroare de sintaxă): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mi> <math>f(n)=O(n!)} </mi><mo stretchy="false"> $f(n)=O(n!)$ </mo><mi> $f(n)=O(n!)$ </mi><mo stretchy="false"> $f(n)=O(n!)$ </mo><mo> $f(n)=O(n!)$ </mo><mi> $f(n)=O(n!)$ </mi><mo stretchy="false"> $f(n)=O(n!)$ </mo><mi> $f(n)=O(n!)$ </mi><mo> $f(n)=O(n!)$ </mo><mo stretchy="false"> $f(n)=O(n!)$ </mo></mstyle></mrow> </math>$f(n)=O(n!)$ $f(n)=O(n!)$ </img> este uneori slăbită la Nu s-a putut interpreta (eroare de sintaxă): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mi> <math>f(n)=O\left(n^n\right)} </mi><mo stretchy="false"> $f(n)=O\left(n^{n}\right)$ </mo><mi> $f(n)=O\left(n^{n}\right)$ </mi><mo stretchy="false"> $f(n)=O\left(n^{n}\right)$ </mo><mo> $f(n)=O\left(n^{n}\right)$ </mo><mi> $f(n)=O\left(n^{n}\right)$ </mi><mrow><mo> $f(n)=O\left(n^{n}\right)$ </mo><msup><mi> $f(n)=O\left(n^{n}\right)$ </mi><mrow class="MJX-TeXAtom-ORD"><mi> $f(n)=O\left(n^{n}\right)$ </mi></mrow></msup><mo> $f(n)=O\left(n^{n}\right)$ </mo></mrow></mstyle></mrow> </math>$f(n)=O\left(n^{n}\right)$ $f(n)=O\left(n^{n}\right)$ </img> pentru a obține formule mai simple pentru complexitatea asimptotică. Pentru orice Nu s-a putut interpreta (eroare de sintaxă): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mi> <math>k>0} </mi><mo> $k>0$ </mo><mn> $k>0$ </mn></mstyle></mrow> </math>$k>0$ $k>0$ </img> și Nu s-a putut interpreta (eroare de sintaxă): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mi> <math>c>0} </mi><mo> $c>0$ </mo><mn> $c>0$ </mn></mstyle></mrow> </math>$c>0$ $c>0$ </img> . Nu s-a putut interpreta (eroare de sintaxă): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mi> <math>O(n^c(\log n)^k)} </mi><mo stretchy="false"> $O(n^{c}(\log n)^{k})$ </mo><msup><mi> $O(n^{c}(\log n)^{k})$ </mi><mrow class="MJX-TeXAtom-ORD"><mi> $O(n^{c}(\log n)^{k})$ </mi></mrow></msup><mo stretchy="false"> $O(n^{c}(\log n)^{k})$ </mo><mi> $O(n^{c}(\log n)^{k})$ </mi><mo> $O(n^{c}(\log n)^{k})$ </mo><mi> $O(n^{c}(\log n)^{k})$ </mi><msup><mo stretchy="false"> $O(n^{c}(\log n)^{k})$ </mo><mrow class="MJX-TeXAtom-ORD"><mi> $O(n^{c}(\log n)^{k})$ </mi></mrow></msup><mo stretchy="false"> $O(n^{c}(\log n)^{k})$ </mo></mstyle></mrow> </math>$O(n^{c}(\log n)^{k})$ $O(n^{c}(\log n)^{k})$ </img> este o submulțime a lui Nu s-a putut interpreta (MathML cu fallback pe SVG sau PNG (recomandat pentru browserele moderne și uneltele de accesibilitate): Răspuns incorect („Math extension cannot connect to Restbase.”) de la serverul „http://localhost:6011/ro.wikipedia.org/v1/”:): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mi> <math>O(n^{c+\varepsilon })} </mi><mo stretchy="false"> $O(n^{c+\varepsilon })$ </mo><msup><mi> $O(n^{c+\varepsilon })$ </mi><mrow class="MJX-TeXAtom-ORD"><mi> $O(n^{c+\varepsilon })$ </mi><mo> $O(n^{c+\varepsilon })$ </mo><mi> $O(n^{c+\varepsilon })$ </mi></mrow></msup><mo stretchy="false"> $O(n^{c+\varepsilon })$ </mo></mstyle></mrow> </math>$O(n^{c+\varepsilon })$ $O(n^{c+\varepsilon })$ </img> pentru orice Nu s-a putut interpreta (eroare de sintaxă): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mi> <math> \varepsilon >0} </mi><mo> $\varepsilon >0$ </mo><mn> $\varepsilon >0$ </mn></mstyle></mrow> </math>$\varepsilon >0$ $\varepsilon >0$ </img> , 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 „f(x) este o(g(x))” (a se citi f(x) este little-o de g(x) înseamnă că g(x) crește mult mai rapid decât f(x). Fie f ca înainte o funcție cu valori reale sau complexe și g o funcție cu valori reale, ambele fiind definite pe unele submulțimi nemărginite ale numerelor reale pozitive, astfel încât g(x) să fie strict pozitivă pentru toate valorile suficient de mari ale lui x. Se scrie

Nu s-a putut interpreta (eroare de sintaxă): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mi> <math>f(x)=o(g(x))\text{ as }x\to\infty} </mi><mo stretchy="false"> $f(x)=o(g(x)){\text{ as }}x\to \infty$ </mo><mi> $f(x)=o(g(x)){\text{ as }}x\to \infty$ </mi><mo stretchy="false"> $f(x)=o(g(x)){\text{ as }}x\to \infty$ </mo><mo> $f(x)=o(g(x)){\text{ as }}x\to \infty$ </mo><mi> $f(x)=o(g(x)){\text{ as }}x\to \infty$ </mi><mo stretchy="false"> $f(x)=o(g(x)){\text{ as }}x\to \infty$ </mo><mi> $f(x)=o(g(x)){\text{ as }}x\to \infty$ </mi><mo stretchy="false"> $f(x)=o(g(x)){\text{ as }}x\to \infty$ </mo><mi> $f(x)=o(g(x)){\text{ as }}x\to \infty$ </mi><mo stretchy="false"> $f(x)=o(g(x)){\text{ as }}x\to \infty$ </mo><mo stretchy="false"> $f(x)=o(g(x)){\text{ as }}x\to \infty$ </mo><mrow class="MJX-TeXAtom-ORD"><mtext> $f(x)=o(g(x)){\text{ as }}x\to \infty$ </mtext></mrow><mi> $f(x)=o(g(x)){\text{ as }}x\to \infty$ </mi><mo stretchy="false"> $f(x)=o(g(x)){\text{ as }}x\to \infty$ </mo><mi mathvariant="normal"> $f(x)=o(g(x)){\text{ as }}x\to \infty$ </mi></mstyle></mrow> </math>$f(x)=o(g(x)){\text{ as }}x\to \infty$ $f(x)=o(g(x)){\text{ as }}x\to \infty$ </img>

dacă pentru orice constantă pozitivă ε există o constantă N astfel încât

<mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mrow class="MJX-TeXAtom-ORD"><mo stretchy="false"> $|f(x)|\leq \varepsilon g(x)\qquad {\text{ for all }}x\geq N~.$ </mo></mrow><mi> $|f(x)|\leq \varepsilon g(x)\qquad {\text{ for all }}x\geq N~.$ </mi><mo stretchy="false"> $|f(x)|\leq \varepsilon g(x)\qquad {\text{ for all }}x\geq N~.$ </mo><mi> $|f(x)|\leq \varepsilon g(x)\qquad {\text{ for all }}x\geq N~.$ </mi><mo stretchy="false"> $|f(x)|\leq \varepsilon g(x)\qquad {\text{ for all }}x\geq N~.$ </mo><mrow class="MJX-TeXAtom-ORD"><mo stretchy="false"> $|f(x)|\leq \varepsilon g(x)\qquad {\text{ for all }}x\geq N~.$ </mo></mrow><mo> $|f(x)|\leq \varepsilon g(x)\qquad {\text{ for all }}x\geq N~.$ </mo><mi> $|f(x)|\leq \varepsilon g(x)\qquad {\text{ for all }}x\geq N~.$ </mi><mi> $|f(x)|\leq \varepsilon g(x)\qquad {\text{ for all }}x\geq N~.$ </mi><mo stretchy="false"> $|f(x)|\leq \varepsilon g(x)\qquad {\text{ for all }}x\geq N~.$ </mo><mi> $|f(x)|\leq \varepsilon g(x)\qquad {\text{ for all }}x\geq N~.$ </mi><mo stretchy="false"> $|f(x)|\leq \varepsilon g(x)\qquad {\text{ for all }}x\geq N~.$ </mo><mrow class="MJX-TeXAtom-ORD"><mtext> $|f(x)|\leq \varepsilon g(x)\qquad {\text{ for all }}x\geq N~.$ </mtext></mrow><mi> $|f(x)|\leq \varepsilon g(x)\qquad {\text{ for all }}x\geq N~.$ </mi><mo> $|f(x)|\leq \varepsilon g(x)\qquad {\text{ for all }}x\geq N~.$ </mo><mi> $|f(x)|\leq \varepsilon g(x)\qquad {\text{ for all }}x\geq N~.$ </mi><mo> $|f(x)|\leq \varepsilon g(x)\qquad {\text{ for all }}x\geq N~.$ </mo></mstyle></mrow> $|f(x)|\leq \varepsilon g(x)\qquad {\text{ for all }}x\geq N~.$ ${\displaystyle }$$|f(x)|\leq \varepsilon g(x)\qquad {\text{ for all }}x\geq N~.$ $|f(x)|\leq \varepsilon g(x)\qquad {\text{ for all }}x\geq N~.$ </img>

De exemplu, avem

Nu s-a putut interpreta (eroare de sintaxă): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mn> <math>2x = o(x^2) } </mn><mi> $2x=o(x^{2})$ </mi><mo> $2x=o(x^{2})$ </mo><mi> $2x=o(x^{2})$ </mi><mo stretchy="false"> $2x=o(x^{2})$ </mo><msup><mi> $2x=o(x^{2})$ </mi><mrow class="MJX-TeXAtom-ORD"><mn> $2x=o(x^{2})$ </mn></mrow></msup><mo stretchy="false"> $2x=o(x^{2})$ </mo></mstyle></mrow> </math>$2x=o(x^{2})$ $2x=o(x^{2})$ </img> și Nu s-a putut interpreta (eroare de sintaxă): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mn> <math>1/x = o(1).} </mn><mrow class="MJX-TeXAtom-ORD"><mo> $1/x=o(1).$ </mo></mrow><mi> $1/x=o(1).$ </mi><mo> $1/x=o(1).$ </mo><mi> $1/x=o(1).$ </mi><mo stretchy="false"> $1/x=o(1).$ </mo><mn> $1/x=o(1).$ </mn><mo stretchy="false"> $1/x=o(1).$ </mo><mo> $1/x=o(1).$ </mo></mstyle></mrow> </math>$1/x=o(1).$ ${\displaystyle }$$1/x=o(1).$ $1/x=o(1).$ </img>

Diferența dintre 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ă M, aceasta din urmă trebuie să fie valabilă pentru orice constantă pozitivă ε , oricât de mică ar fi. Î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 g este de asemenea big O al lui g, dar nu orice funcție care este big-O al lui g este și little-o de g. De exemplu, Nu s-a putut interpreta (eroare de sintaxă): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mn> <math>2x^2 = O(x^2) } </mn><msup><mi> $2x^{2}=O(x^{2})$ </mi><mrow class="MJX-TeXAtom-ORD"><mn> $2x^{2}=O(x^{2})$ </mn></mrow></msup><mo> $2x^{2}=O(x^{2})$ </mo><mi> $2x^{2}=O(x^{2})$ </mi><mo stretchy="false"> $2x^{2}=O(x^{2})$ </mo><msup><mi> $2x^{2}=O(x^{2})$ </mi><mrow class="MJX-TeXAtom-ORD"><mn> $2x^{2}=O(x^{2})$ </mn></mrow></msup><mo stretchy="false"> $2x^{2}=O(x^{2})$ </mo></mstyle></mrow> </math>$2x^{2}=O(x^{2})$ $2x^{2}=O(x^{2})$ </img> dar Nu s-a putut interpreta (eroare de sintaxă): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mn> <math>2x^2 \neq o(x^2). } </mn><msup><mi> $2x^{2}\neq o(x^{2}).$ </mi><mrow class="MJX-TeXAtom-ORD"><mn> $2x^{2}\neq o(x^{2}).$ </mn></mrow></msup><mo> $2x^{2}\neq o(x^{2}).$ </mo><mi> $2x^{2}\neq o(x^{2}).$ </mi><mo stretchy="false"> $2x^{2}\neq o(x^{2}).$ </mo><msup><mi> $2x^{2}\neq o(x^{2}).$ </mi><mrow class="MJX-TeXAtom-ORD"><mn> $2x^{2}\neq o(x^{2}).$ </mn></mrow></msup><mo stretchy="false"> $2x^{2}\neq o(x^{2}).$ </mo><mo> $2x^{2}\neq o(x^{2}).$ </mo></mstyle></mrow> </math>$2x^{2}\neq o(x^{2}).$ ${\displaystyle }$$2x^{2}\neq o(x^{2}).$ $2x^{2}\neq o(x^{2}).$ </img>

Deoarece g(x) este nenul, sau cel puțin devine nenul dincolo de un anumit punct, relația f(x) = o(g(x)) este echivalentă cu

Nu s-a putut interpreta (eroare de sintaxă): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><munder><mo movablelimits="true"> <math>\lim_{x \to \infty}\frac{f(x)}{g(x)}=0} </mo><mrow class="MJX-TeXAtom-ORD"><mi> $\lim _{x\to \infty }{\frac {f(x)}{g(x)}}=0$ </mi><mo stretchy="false"> $\lim _{x\to \infty }{\frac {f(x)}{g(x)}}=0$ </mo><mi mathvariant="normal"> $\lim _{x\to \infty }{\frac {f(x)}{g(x)}}=0$ </mi></mrow></munder><mrow class="MJX-TeXAtom-ORD"><mfrac><mrow><mi> $\lim _{x\to \infty }{\frac {f(x)}{g(x)}}=0$ </mi><mo stretchy="false"> $\lim _{x\to \infty }{\frac {f(x)}{g(x)}}=0$ </mo><mi> $\lim _{x\to \infty }{\frac {f(x)}{g(x)}}=0$ </mi><mo stretchy="false"> $\lim _{x\to \infty }{\frac {f(x)}{g(x)}}=0$ </mo></mrow><mrow><mi> $\lim _{x\to \infty }{\frac {f(x)}{g(x)}}=0$ </mi><mo stretchy="false"> $\lim _{x\to \infty }{\frac {f(x)}{g(x)}}=0$ </mo><mi> $\lim _{x\to \infty }{\frac {f(x)}{g(x)}}=0$ </mi><mo stretchy="false"> $\lim _{x\to \infty }{\frac {f(x)}{g(x)}}=0$ </mo></mrow></mfrac></mrow><mo> $\lim _{x\to \infty }{\frac {f(x)}{g(x)}}=0$ </mo><mn> $\lim _{x\to \infty }{\frac {f(x)}{g(x)}}=0$ </mn></mstyle></mrow> </math>$\lim _{x\to \infty }{\frac {f(x)}{g(x)}}=0$ $\lim _{x\to \infty }{\frac {f(x)}{g(x)}}=0$ </img> (și așa a definit, de fapt, Landau notația little-o).

Little-o respectă o serie de operații aritmetice. De exemplu,

dacă c este o constantă nenulă și Nu s-a putut interpreta (eroare de sintaxă): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mi> <math>f = o(g)} </mi><mo> $f=o(g)$ </mo><mi> $f=o(g)$ </mi><mo stretchy="false"> $f=o(g)$ </mo><mi> $f=o(g)$ </mi><mo stretchy="false"> $f=o(g)$ </mo></mstyle></mrow> </math>$f=o(g)$ $f=o(g)$ </img> atunci Nu s-a putut interpreta (eroare de sintaxă): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mi> <math>c \cdot f = o(g)} </mi><mo> $c\cdot f=o(g)$ </mo><mi> $c\cdot f=o(g)$ </mi><mo> $c\cdot f=o(g)$ </mo><mi> $c\cdot f=o(g)$ </mi><mo stretchy="false"> $c\cdot f=o(g)$ </mo><mi> $c\cdot f=o(g)$ </mi><mo stretchy="false"> $c\cdot f=o(g)$ </mo></mstyle></mrow> </math>$c\cdot f=o(g)$ $c\cdot f=o(g)$ </img> , și

dacă Nu s-a putut interpreta (eroare de sintaxă): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mi> <math>f = o(F)} </mi><mo> $f=o(F)$ </mo><mi> $f=o(F)$ </mi><mo stretchy="false"> $f=o(F)$ </mo><mi> $f=o(F)$ </mi><mo stretchy="false"> $f=o(F)$ </mo></mstyle></mrow> </math>$f=o(F)$ $f=o(F)$ </img> și Nu s-a putut interpreta (eroare de sintaxă): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mi> <math>g = o(G)} </mi><mo> $g=o(G)$ </mo><mi> $g=o(G)$ </mi><mo stretchy="false"> $g=o(G)$ </mo><mi> $g=o(G)$ </mi><mo stretchy="false"> $g=o(G)$ </mo></mstyle></mrow> </math>$g=o(G)$ $g=o(G)$ </img> atunci Nu s-a putut interpreta (eroare de sintaxă): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mi> <math> f \cdot g = o(F \cdot G).} </mi><mo> $f\cdot g=o(F\cdot G).$ </mo><mi> $f\cdot g=o(F\cdot G).$ </mi><mo> $f\cdot g=o(F\cdot G).$ </mo><mi> $f\cdot g=o(F\cdot G).$ </mi><mo stretchy="false"> $f\cdot g=o(F\cdot G).$ </mo><mi> $f\cdot g=o(F\cdot G).$ </mi><mo> $f\cdot g=o(F\cdot G).$ </mo><mi> $f\cdot g=o(F\cdot G).$ </mi><mo stretchy="false"> $f\cdot g=o(F\cdot G).$ </mo><mo> $f\cdot g=o(F\cdot G).$ </mo></mstyle></mrow> </math>$f\cdot g=o(F\cdot G).$ ${\displaystyle }$$f\cdot g=o(F\cdot G).$ $f\cdot g=o(F\cdot G).$ </img>

De asemenea, satisface o relație de tranzitivitate:

dacă Nu s-a putut interpreta (eroare de sintaxă): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mi> <math> f = o(g)} </mi><mo> $f=o(g)$ </mo><mi> $f=o(g)$ </mi><mo stretchy="false"> $f=o(g)$ </mo><mi> $f=o(g)$ </mi><mo stretchy="false"> $f=o(g)$ </mo></mstyle></mrow> </math>$f=o(g)$ $f=o(g)$ </img> și Nu s-a putut interpreta (eroare de sintaxă): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mi> <math> g = o(h)} </mi><mo> $g=o(h)$ </mo><mi> $g=o(h)$ </mi><mo stretchy="false"> $g=o(h)$ </mo><mi> $g=o(h)$ </mi><mo stretchy="false"> $g=o(h)$ </mo></mstyle></mrow> </math>$g=o(h)$ $g=o(h)$ </img> atunci Nu s-a putut interpreta (eroare de sintaxă): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mi> <math> f = o(h).} </mi><mo> $f=o(h).$ </mo><mi> $f=o(h).$ </mi><mo stretchy="false"> $f=o(h).$ </mo><mi> $f=o(h).$ </mi><mo stretchy="false"> $f=o(h).$ </mo><mo> $f=o(h).$ </mo></mstyle></mrow> </math>$f=o(h).$ ${\displaystyle }$$f=o(h).$ $f=o(h).$ </img>

Notația Big Omega

Există două definiții foarte răspândite și incompatibile ale afirmației

Nu s-a putut interpreta (eroare de sintaxă): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mi> <math>f(x)=\Omega(g(x))\ (x\rightarrow a),} </mi><mo stretchy="false"> $f(x)=\Omega (g(x))\ (x\rightarrow a),$ </mo><mi> $f(x)=\Omega (g(x))\ (x\rightarrow a),$ </mi><mo stretchy="false"> $f(x)=\Omega (g(x))\ (x\rightarrow a),$ </mo><mo> $f(x)=\Omega (g(x))\ (x\rightarrow a),$ </mo><mi mathvariant="normal"> $f(x)=\Omega (g(x))\ (x\rightarrow a),$ </mi><mo stretchy="false"> $f(x)=\Omega (g(x))\ (x\rightarrow a),$ </mo><mi> $f(x)=\Omega (g(x))\ (x\rightarrow a),$ </mi><mo stretchy="false"> $f(x)=\Omega (g(x))\ (x\rightarrow a),$ </mo><mi> $f(x)=\Omega (g(x))\ (x\rightarrow a),$ </mi><mo stretchy="false"> $f(x)=\Omega (g(x))\ (x\rightarrow a),$ </mo><mo stretchy="false"> $f(x)=\Omega (g(x))\ (x\rightarrow a),$ </mo><mo stretchy="false"> $f(x)=\Omega (g(x))\ (x\rightarrow a),$ </mo><mi> $f(x)=\Omega (g(x))\ (x\rightarrow a),$ </mi><mo stretchy="false"> $f(x)=\Omega (g(x))\ (x\rightarrow a),$ </mo><mi> $f(x)=\Omega (g(x))\ (x\rightarrow a),$ </mi><mo stretchy="false"> $f(x)=\Omega (g(x))\ (x\rightarrow a),$ </mo><mo> $f(x)=\Omega (g(x))\ (x\rightarrow a),$ </mo></mstyle></mrow> </math>$f(x)=\Omega (g(x))\ (x\rightarrow a),$ $f(x)=\Omega (g(x))\ (x\rightarrow a),$ </img>

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

Primul (cronologic) este folosită în teoria numerelor analitice, 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, Godfrey Harold Hardy și John Edensor Littlewood au introdus noul simbol Nu s-a putut interpreta (eroare de sintaxă): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mi mathvariant="normal"> <math>\Omega} </mi></mstyle></mrow> </math>$\Omega$ $\Omega$ </img> , care este definit după cum urmează:

<mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mi> $f(x)=\Omega (g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\limsup _{x\to \infty }\left|{\frac {f(x)}{g(x)}}\right|>0.$ </mi><mo stretchy="false"> $f(x)=\Omega (g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\limsup _{x\to \infty }\left|{\frac {f(x)}{g(x)}}\right|>0.$ </mo><mi> $f(x)=\Omega (g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\limsup _{x\to \infty }\left|{\frac {f(x)}{g(x)}}\right|>0.$ </mi><mo stretchy="false"> $f(x)=\Omega (g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\limsup _{x\to \infty }\left|{\frac {f(x)}{g(x)}}\right|>0.$ </mo><mo> $f(x)=\Omega (g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\limsup _{x\to \infty }\left|{\frac {f(x)}{g(x)}}\right|>0.$ </mo><mi mathvariant="normal"> $f(x)=\Omega (g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\limsup _{x\to \infty }\left|{\frac {f(x)}{g(x)}}\right|>0.$ </mi><mo stretchy="false"> $f(x)=\Omega (g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\limsup _{x\to \infty }\left|{\frac {f(x)}{g(x)}}\right|>0.$ </mo><mi> $f(x)=\Omega (g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\limsup _{x\to \infty }\left|{\frac {f(x)}{g(x)}}\right|>0.$ </mi><mo stretchy="false"> $f(x)=\Omega (g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\limsup _{x\to \infty }\left|{\frac {f(x)}{g(x)}}\right|>0.$ </mo><mi> $f(x)=\Omega (g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\limsup _{x\to \infty }\left|{\frac {f(x)}{g(x)}}\right|>0.$ </mi><mo stretchy="false"> $f(x)=\Omega (g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\limsup _{x\to \infty }\left|{\frac {f(x)}{g(x)}}\right|>0.$ </mo><mo stretchy="false"> $f(x)=\Omega (g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\limsup _{x\to \infty }\left|{\frac {f(x)}{g(x)}}\right|>0.$ </mo><mo stretchy="false"> $f(x)=\Omega (g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\limsup _{x\to \infty }\left|{\frac {f(x)}{g(x)}}\right|>0.$ </mo><mi> $f(x)=\Omega (g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\limsup _{x\to \infty }\left|{\frac {f(x)}{g(x)}}\right|>0.$ </mi><mo stretchy="false"> $f(x)=\Omega (g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\limsup _{x\to \infty }\left|{\frac {f(x)}{g(x)}}\right|>0.$ </mo><mi mathvariant="normal"> $f(x)=\Omega (g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\limsup _{x\to \infty }\left|{\frac {f(x)}{g(x)}}\right|>0.$ </mi><mo stretchy="false"> $f(x)=\Omega (g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\limsup _{x\to \infty }\left|{\frac {f(x)}{g(x)}}\right|>0.$ </mo><mo stretchy="false"> $f(x)=\Omega (g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\limsup _{x\to \infty }\left|{\frac {f(x)}{g(x)}}\right|>0.$ </mo><munder><mo movablelimits="true"> $f(x)=\Omega (g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\limsup _{x\to \infty }\left|{\frac {f(x)}{g(x)}}\right|>0.$ </mo><mrow class="MJX-TeXAtom-ORD"><mi> $f(x)=\Omega (g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\limsup _{x\to \infty }\left|{\frac {f(x)}{g(x)}}\right|>0.$ </mi><mo stretchy="false"> $f(x)=\Omega (g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\limsup _{x\to \infty }\left|{\frac {f(x)}{g(x)}}\right|>0.$ </mo><mi mathvariant="normal"> $f(x)=\Omega (g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\limsup _{x\to \infty }\left|{\frac {f(x)}{g(x)}}\right|>0.$ </mi></mrow></munder><mrow><mo> $f(x)=\Omega (g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\limsup _{x\to \infty }\left|{\frac {f(x)}{g(x)}}\right|>0.$ </mo><mrow class="MJX-TeXAtom-ORD"><mfrac><mrow><mi> $f(x)=\Omega (g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\limsup _{x\to \infty }\left|{\frac {f(x)}{g(x)}}\right|>0.$ </mi><mo stretchy="false"> $f(x)=\Omega (g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\limsup _{x\to \infty }\left|{\frac {f(x)}{g(x)}}\right|>0.$ </mo><mi> $f(x)=\Omega (g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\limsup _{x\to \infty }\left|{\frac {f(x)}{g(x)}}\right|>0.$ </mi><mo stretchy="false"> $f(x)=\Omega (g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\limsup _{x\to \infty }\left|{\frac {f(x)}{g(x)}}\right|>0.$ </mo></mrow><mrow><mi> $f(x)=\Omega (g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\limsup _{x\to \infty }\left|{\frac {f(x)}{g(x)}}\right|>0.$ </mi><mo stretchy="false"> $f(x)=\Omega (g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\limsup _{x\to \infty }\left|{\frac {f(x)}{g(x)}}\right|>0.$ </mo><mi> $f(x)=\Omega (g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\limsup _{x\to \infty }\left|{\frac {f(x)}{g(x)}}\right|>0.$ </mi><mo stretchy="false"> $f(x)=\Omega (g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\limsup _{x\to \infty }\left|{\frac {f(x)}{g(x)}}\right|>0.$ </mo></mrow></mfrac></mrow><mo> $f(x)=\Omega (g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\limsup _{x\to \infty }\left|{\frac {f(x)}{g(x)}}\right|>0.$ </mo></mrow><mo> $f(x)=\Omega (g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\limsup _{x\to \infty }\left|{\frac {f(x)}{g(x)}}\right|>0.$ </mo><mn> $f(x)=\Omega (g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\limsup _{x\to \infty }\left|{\frac {f(x)}{g(x)}}\right|>0.$ </mn></mstyle></mrow> $f(x)=\Omega (g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\limsup _{x\to \infty }\left|{\frac {f(x)}{g(x)}}\right|>0.$ ${\displaystyle }$$f(x)=\Omega (g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\limsup _{x\to \infty }\left|{\frac {f(x)}{g(x)}}\right|>0.$ $f(x)=\Omega (g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\limsup _{x\to \infty }\left|{\frac {f(x)}{g(x)}}\right|>0.$ </img>

Prin urmare Nu s-a putut interpreta (MathML cu fallback pe SVG sau PNG (recomandat pentru browserele moderne și uneltele de accesibilitate): Răspuns incorect („Math extension cannot connect to Restbase.”) de la serverul „http://localhost:6011/ro.wikipedia.org/v1/”:): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mi> <math>f(x)=\Omega(g(x))} </mi><mo stretchy="false"> $f(x)=\Omega (g(x))$ </mo><mi> $f(x)=\Omega (g(x))$ </mi><mo stretchy="false"> $f(x)=\Omega (g(x))$ </mo><mo> $f(x)=\Omega (g(x))$ </mo><mi mathvariant="normal"> $f(x)=\Omega (g(x))$ </mi><mo stretchy="false"> $f(x)=\Omega (g(x))$ </mo><mi> $f(x)=\Omega (g(x))$ </mi><mo stretchy="false"> $f(x)=\Omega (g(x))$ </mo><mi> $f(x)=\Omega (g(x))$ </mi><mo stretchy="false"> $f(x)=\Omega (g(x))$ </mo><mo stretchy="false"> $f(x)=\Omega (g(x))$ </mo></mstyle></mrow> </math>$f(x)=\Omega (g(x))$ $f(x)=\Omega (g(x))$ </img> este negarea lui Nu s-a putut interpreta (eroare de sintaxă): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mi> <math>f(x)=o(g(x))} </mi><mo stretchy="false"> $f(x)=o(g(x))$ </mo><mi> $f(x)=o(g(x))$ </mi><mo stretchy="false"> $f(x)=o(g(x))$ </mo><mo> $f(x)=o(g(x))$ </mo><mi> $f(x)=o(g(x))$ </mi><mo stretchy="false"> $f(x)=o(g(x))$ </mo><mi> $f(x)=o(g(x))$ </mi><mo stretchy="false"> $f(x)=o(g(x))$ </mo><mi> $f(x)=o(g(x))$ </mi><mo stretchy="false"> $f(x)=o(g(x))$ </mo><mo stretchy="false"> $f(x)=o(g(x))$ </mo></mstyle></mrow> </math>$f(x)=o(g(x))$ $f(x)=o(g(x))$ </img> .

În 1916, aceiași autori au introdus cele două noi simboluri Nu s-a putut interpreta (eroare de sintaxă): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><msub><mi mathvariant="normal"> <math>\Omega_R} </mi><mrow class="MJX-TeXAtom-ORD"><mi> $\Omega _{R}$ </mi></mrow></msub></mstyle></mrow> </math>$\Omega _{R}$ $\Omega _{R}$ </img> și Nu s-a putut interpreta (eroare de sintaxă): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><msub><mi mathvariant="normal"> <math>\Omega_L} </mi><mrow class="MJX-TeXAtom-ORD"><mi> $\Omega _{L}$ </mi></mrow></msub></mstyle></mrow> </math>$\Omega _{L}$ $\Omega _{L}$ </img> , definite astfel:

Nu s-a putut interpreta (eroare de sintaxă): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mi> <math>f(x)=\Omega_R(g(x))\ (x\rightarrow\infty)\;\Leftrightarrow\;\limsup_{x \to \infty} \frac{f(x)}{g(x)}> 0} </mi><mo stretchy="false"> $f(x)=\Omega _{R}(g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\limsup _{x\to \infty }{\frac {f(x)}{g(x)}}>0$ </mo><mi> $f(x)=\Omega _{R}(g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\limsup _{x\to \infty }{\frac {f(x)}{g(x)}}>0$ </mi><mo stretchy="false"> $f(x)=\Omega _{R}(g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\limsup _{x\to \infty }{\frac {f(x)}{g(x)}}>0$ </mo><mo> $f(x)=\Omega _{R}(g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\limsup _{x\to \infty }{\frac {f(x)}{g(x)}}>0$ </mo><msub><mi mathvariant="normal"> $f(x)=\Omega _{R}(g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\limsup _{x\to \infty }{\frac {f(x)}{g(x)}}>0$ </mi><mrow class="MJX-TeXAtom-ORD"><mi> $f(x)=\Omega _{R}(g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\limsup _{x\to \infty }{\frac {f(x)}{g(x)}}>0$ </mi></mrow></msub><mo stretchy="false"> $f(x)=\Omega _{R}(g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\limsup _{x\to \infty }{\frac {f(x)}{g(x)}}>0$ </mo><mi> $f(x)=\Omega _{R}(g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\limsup _{x\to \infty }{\frac {f(x)}{g(x)}}>0$ </mi><mo stretchy="false"> $f(x)=\Omega _{R}(g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\limsup _{x\to \infty }{\frac {f(x)}{g(x)}}>0$ </mo><mi> $f(x)=\Omega _{R}(g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\limsup _{x\to \infty }{\frac {f(x)}{g(x)}}>0$ </mi><mo stretchy="false"> $f(x)=\Omega _{R}(g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\limsup _{x\to \infty }{\frac {f(x)}{g(x)}}>0$ </mo><mo stretchy="false"> $f(x)=\Omega _{R}(g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\limsup _{x\to \infty }{\frac {f(x)}{g(x)}}>0$ </mo><mo stretchy="false"> $f(x)=\Omega _{R}(g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\limsup _{x\to \infty }{\frac {f(x)}{g(x)}}>0$ </mo><mi> $f(x)=\Omega _{R}(g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\limsup _{x\to \infty }{\frac {f(x)}{g(x)}}>0$ </mi><mo stretchy="false"> $f(x)=\Omega _{R}(g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\limsup _{x\to \infty }{\frac {f(x)}{g(x)}}>0$ </mo><mi mathvariant="normal"> $f(x)=\Omega _{R}(g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\limsup _{x\to \infty }{\frac {f(x)}{g(x)}}>0$ </mi><mo stretchy="false"> $f(x)=\Omega _{R}(g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\limsup _{x\to \infty }{\frac {f(x)}{g(x)}}>0$ </mo><mo stretchy="false"> $f(x)=\Omega _{R}(g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\limsup _{x\to \infty }{\frac {f(x)}{g(x)}}>0$ </mo><munder><mo movablelimits="true"> $f(x)=\Omega _{R}(g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\limsup _{x\to \infty }{\frac {f(x)}{g(x)}}>0$ </mo><mrow class="MJX-TeXAtom-ORD"><mi> $f(x)=\Omega _{R}(g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\limsup _{x\to \infty }{\frac {f(x)}{g(x)}}>0$ </mi><mo stretchy="false"> $f(x)=\Omega _{R}(g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\limsup _{x\to \infty }{\frac {f(x)}{g(x)}}>0$ </mo><mi mathvariant="normal"> $f(x)=\Omega _{R}(g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\limsup _{x\to \infty }{\frac {f(x)}{g(x)}}>0$ </mi></mrow></munder><mrow class="MJX-TeXAtom-ORD"><mfrac><mrow><mi> $f(x)=\Omega _{R}(g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\limsup _{x\to \infty }{\frac {f(x)}{g(x)}}>0$ </mi><mo stretchy="false"> $f(x)=\Omega _{R}(g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\limsup _{x\to \infty }{\frac {f(x)}{g(x)}}>0$ </mo><mi> $f(x)=\Omega _{R}(g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\limsup _{x\to \infty }{\frac {f(x)}{g(x)}}>0$ </mi><mo stretchy="false"> $f(x)=\Omega _{R}(g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\limsup _{x\to \infty }{\frac {f(x)}{g(x)}}>0$ </mo></mrow><mrow><mi> $f(x)=\Omega _{R}(g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\limsup _{x\to \infty }{\frac {f(x)}{g(x)}}>0$ </mi><mo stretchy="false"> $f(x)=\Omega _{R}(g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\limsup _{x\to \infty }{\frac {f(x)}{g(x)}}>0$ </mo><mi> $f(x)=\Omega _{R}(g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\limsup _{x\to \infty }{\frac {f(x)}{g(x)}}>0$ </mi><mo stretchy="false"> $f(x)=\Omega _{R}(g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\limsup _{x\to \infty }{\frac {f(x)}{g(x)}}>0$ </mo></mrow></mfrac></mrow><mo> $f(x)=\Omega _{R}(g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\limsup _{x\to \infty }{\frac {f(x)}{g(x)}}>0$ </mo><mn> $f(x)=\Omega _{R}(g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\limsup _{x\to \infty }{\frac {f(x)}{g(x)}}>0$ </mn></mstyle></mrow> </math>$f(x)=\Omega _{R}(g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\limsup _{x\to \infty }{\frac {f(x)}{g(x)}}>0$ $f(x)=\Omega _{R}(g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\limsup _{x\to \infty }{\frac {f(x)}{g(x)}}>0$ </img>  ;

<mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mi> $f(x)=\Omega _{L}(g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\liminf _{x\to \infty }{\frac {f(x)}{g(x)}}<0.$ </mi><mo stretchy="false"> $f(x)=\Omega _{L}(g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\liminf _{x\to \infty }{\frac {f(x)}{g(x)}}<0.$ </mo><mi> $f(x)=\Omega _{L}(g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\liminf _{x\to \infty }{\frac {f(x)}{g(x)}}<0.$ </mi><mo stretchy="false"> $f(x)=\Omega _{L}(g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\liminf _{x\to \infty }{\frac {f(x)}{g(x)}}<0.$ </mo><mo> $f(x)=\Omega _{L}(g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\liminf _{x\to \infty }{\frac {f(x)}{g(x)}}<0.$ </mo><msub><mi mathvariant="normal"> $f(x)=\Omega _{L}(g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\liminf _{x\to \infty }{\frac {f(x)}{g(x)}}<0.$ </mi><mrow class="MJX-TeXAtom-ORD"><mi> $f(x)=\Omega _{L}(g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\liminf _{x\to \infty }{\frac {f(x)}{g(x)}}<0.$ </mi></mrow></msub><mo stretchy="false"> $f(x)=\Omega _{L}(g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\liminf _{x\to \infty }{\frac {f(x)}{g(x)}}<0.$ </mo><mi> $f(x)=\Omega _{L}(g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\liminf _{x\to \infty }{\frac {f(x)}{g(x)}}<0.$ </mi><mo stretchy="false"> $f(x)=\Omega _{L}(g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\liminf _{x\to \infty }{\frac {f(x)}{g(x)}}<0.$ </mo><mi> $f(x)=\Omega _{L}(g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\liminf _{x\to \infty }{\frac {f(x)}{g(x)}}<0.$ </mi><mo stretchy="false"> $f(x)=\Omega _{L}(g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\liminf _{x\to \infty }{\frac {f(x)}{g(x)}}<0.$ </mo><mo stretchy="false"> $f(x)=\Omega _{L}(g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\liminf _{x\to \infty }{\frac {f(x)}{g(x)}}<0.$ </mo><mo stretchy="false"> $f(x)=\Omega _{L}(g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\liminf _{x\to \infty }{\frac {f(x)}{g(x)}}<0.$ </mo><mi> $f(x)=\Omega _{L}(g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\liminf _{x\to \infty }{\frac {f(x)}{g(x)}}<0.$ </mi><mo stretchy="false"> $f(x)=\Omega _{L}(g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\liminf _{x\to \infty }{\frac {f(x)}{g(x)}}<0.$ </mo><mi mathvariant="normal"> $f(x)=\Omega _{L}(g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\liminf _{x\to \infty }{\frac {f(x)}{g(x)}}<0.$ </mi><mo stretchy="false"> $f(x)=\Omega _{L}(g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\liminf _{x\to \infty }{\frac {f(x)}{g(x)}}<0.$ </mo><mo stretchy="false"> $f(x)=\Omega _{L}(g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\liminf _{x\to \infty }{\frac {f(x)}{g(x)}}<0.$ </mo><munder><mo movablelimits="true"> $f(x)=\Omega _{L}(g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\liminf _{x\to \infty }{\frac {f(x)}{g(x)}}<0.$ </mo><mrow class="MJX-TeXAtom-ORD"><mi> $f(x)=\Omega _{L}(g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\liminf _{x\to \infty }{\frac {f(x)}{g(x)}}<0.$ </mi><mo stretchy="false"> $f(x)=\Omega _{L}(g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\liminf _{x\to \infty }{\frac {f(x)}{g(x)}}<0.$ </mo><mi mathvariant="normal"> $f(x)=\Omega _{L}(g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\liminf _{x\to \infty }{\frac {f(x)}{g(x)}}<0.$ </mi></mrow></munder><mrow class="MJX-TeXAtom-ORD"><mfrac><mrow><mi> $f(x)=\Omega _{L}(g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\liminf _{x\to \infty }{\frac {f(x)}{g(x)}}<0.$ </mi><mo stretchy="false"> $f(x)=\Omega _{L}(g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\liminf _{x\to \infty }{\frac {f(x)}{g(x)}}<0.$ </mo><mi> $f(x)=\Omega _{L}(g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\liminf _{x\to \infty }{\frac {f(x)}{g(x)}}<0.$ </mi><mo stretchy="false"> $f(x)=\Omega _{L}(g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\liminf _{x\to \infty }{\frac {f(x)}{g(x)}}<0.$ </mo></mrow><mrow><mi> $f(x)=\Omega _{L}(g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\liminf _{x\to \infty }{\frac {f(x)}{g(x)}}<0.$ </mi><mo stretchy="false"> $f(x)=\Omega _{L}(g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\liminf _{x\to \infty }{\frac {f(x)}{g(x)}}<0.$ </mo><mi> $f(x)=\Omega _{L}(g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\liminf _{x\to \infty }{\frac {f(x)}{g(x)}}<0.$ </mi><mo stretchy="false"> $f(x)=\Omega _{L}(g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\liminf _{x\to \infty }{\frac {f(x)}{g(x)}}<0.$ </mo></mrow></mfrac></mrow><mo> $f(x)=\Omega _{L}(g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\liminf _{x\to \infty }{\frac {f(x)}{g(x)}}<0.$ </mo><mn> $f(x)=\Omega _{L}(g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\liminf _{x\to \infty }{\frac {f(x)}{g(x)}}<0.$ </mn></mstyle></mrow> $f(x)=\Omega _{L}(g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\liminf _{x\to \infty }{\frac {f(x)}{g(x)}}<0.$ ${\displaystyle }$$f(x)=\Omega _{L}(g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\liminf _{x\to \infty }{\frac {f(x)}{g(x)}}<0.$ $f(x)=\Omega _{L}(g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\liminf _{x\to \infty }{\frac {f(x)}{g(x)}}<0.$ </img>

Aceste simboluri au fost folosite de Edmund Landau, cu aceleași semnificații, în 1924. După Landau, notațiile nu au fost niciodată folosite din nou exact așa; Nu s-a putut interpreta (eroare de sintaxă): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><msub><mi mathvariant="normal"> <math>\Omega_R} </mi><mrow class="MJX-TeXAtom-ORD"><mi> $\Omega _{R}$ </mi></mrow></msub></mstyle></mrow> </math>$\Omega _{R}$ $\Omega _{R}$ </img> a devenit Nu s-a putut interpreta (eroare de sintaxă): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><msub><mi mathvariant="normal"> <math>\Omega_+} </mi><mrow class="MJX-TeXAtom-ORD"><mo> $\Omega _{+}$ </mo></mrow></msub></mstyle></mrow> </math>$\Omega _{+}$ $\Omega _{+}$ </img> și Nu s-a putut interpreta (eroare de sintaxă): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><msub><mi mathvariant="normal"> <math>\Omega_L} </mi><mrow class="MJX-TeXAtom-ORD"><mi> $\Omega _{L}$ </mi></mrow></msub></mstyle></mrow> </math>$\Omega _{L}$ $\Omega _{L}$ </img> a devenit Nu s-a putut interpreta (eroare de sintaxă): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><msub><mi mathvariant="normal"> <math>\Omega_-} </mi><mrow class="MJX-TeXAtom-ORD"><mo> $\Omega _{-}$ </mo></mrow></msub></mstyle></mrow> </math>$\Omega _{-}$ $\Omega _{-}$ </img> .  

Aceste trei simboluri Nu s-a putut interpreta (eroare de sintaxă): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mi mathvariant="normal"> <math>\Omega, \Omega_+, \Omega_-} </mi><mo> $\Omega ,\Omega _{+},\Omega _{-}$ </mo><msub><mi mathvariant="normal"> $\Omega ,\Omega _{+},\Omega _{-}$ </mi><mrow class="MJX-TeXAtom-ORD"><mo> $\Omega ,\Omega _{+},\Omega _{-}$ </mo></mrow></msub><mo> $\Omega ,\Omega _{+},\Omega _{-}$ </mo><msub><mi mathvariant="normal"> $\Omega ,\Omega _{+},\Omega _{-}$ </mi><mrow class="MJX-TeXAtom-ORD"><mo> $\Omega ,\Omega _{+},\Omega _{-}$ </mo></mrow></msub></mstyle></mrow> </math>$\Omega ,\Omega _{+},\Omega _{-}$ $\Omega ,\Omega _{+},\Omega _{-}$ </img> , precum și Nu s-a putut interpreta (eroare de sintaxă): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mi> <math>f(x)=\Omega_\pm(g(x))} </mi><mo stretchy="false"> $f(x)=\Omega _{\pm }(g(x))$ </mo><mi> $f(x)=\Omega _{\pm }(g(x))$ </mi><mo stretchy="false"> $f(x)=\Omega _{\pm }(g(x))$ </mo><mo> $f(x)=\Omega _{\pm }(g(x))$ </mo><msub><mi mathvariant="normal"> $f(x)=\Omega _{\pm }(g(x))$ </mi><mrow class="MJX-TeXAtom-ORD"><mo> $f(x)=\Omega _{\pm }(g(x))$ </mo></mrow></msub><mo stretchy="false"> $f(x)=\Omega _{\pm }(g(x))$ </mo><mi> $f(x)=\Omega _{\pm }(g(x))$ </mi><mo stretchy="false"> $f(x)=\Omega _{\pm }(g(x))$ </mo><mi> $f(x)=\Omega _{\pm }(g(x))$ </mi><mo stretchy="false"> $f(x)=\Omega _{\pm }(g(x))$ </mo><mo stretchy="false"> $f(x)=\Omega _{\pm }(g(x))$ </mo></mstyle></mrow> </math>$f(x)=\Omega _{\pm }(g(x))$ $f(x)=\Omega _{\pm }(g(x))$ </img> (ceea ce înseamnă că atât Nu s-a putut interpreta (eroare de sintaxă): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mi> <math>f(x)=\Omega_+(g(x))} </mi><mo stretchy="false"> $f(x)=\Omega _{+}(g(x))$ </mo><mi> $f(x)=\Omega _{+}(g(x))$ </mi><mo stretchy="false"> $f(x)=\Omega _{+}(g(x))$ </mo><mo> $f(x)=\Omega _{+}(g(x))$ </mo><msub><mi mathvariant="normal"> $f(x)=\Omega _{+}(g(x))$ </mi><mrow class="MJX-TeXAtom-ORD"><mo> $f(x)=\Omega _{+}(g(x))$ </mo></mrow></msub><mo stretchy="false"> $f(x)=\Omega _{+}(g(x))$ </mo><mi> $f(x)=\Omega _{+}(g(x))$ </mi><mo stretchy="false"> $f(x)=\Omega _{+}(g(x))$ </mo><mi> $f(x)=\Omega _{+}(g(x))$ </mi><mo stretchy="false"> $f(x)=\Omega _{+}(g(x))$ </mo><mo stretchy="false"> $f(x)=\Omega _{+}(g(x))$ </mo></mstyle></mrow> </math>$f(x)=\Omega _{+}(g(x))$ $f(x)=\Omega _{+}(g(x))$ </img> cât și Nu s-a putut interpreta (eroare de sintaxă): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mi> <math>f(x)=\Omega_-(g(x))} </mi><mo stretchy="false"> $f(x)=\Omega _{-}(g(x))$ </mo><mi> $f(x)=\Omega _{-}(g(x))$ </mi><mo stretchy="false"> $f(x)=\Omega _{-}(g(x))$ </mo><mo> $f(x)=\Omega _{-}(g(x))$ </mo><msub><mi mathvariant="normal"> $f(x)=\Omega _{-}(g(x))$ </mi><mrow class="MJX-TeXAtom-ORD"><mo> $f(x)=\Omega _{-}(g(x))$ </mo></mrow></msub><mo stretchy="false"> $f(x)=\Omega _{-}(g(x))$ </mo><mi> $f(x)=\Omega _{-}(g(x))$ </mi><mo stretchy="false"> $f(x)=\Omega _{-}(g(x))$ </mo><mi> $f(x)=\Omega _{-}(g(x))$ </mi><mo stretchy="false"> $f(x)=\Omega _{-}(g(x))$ </mo><mo stretchy="false"> $f(x)=\Omega _{-}(g(x))$ </mo></mstyle></mrow> </math>$f(x)=\Omega _{-}(g(x))$ $f(x)=\Omega _{-}(g(x))$ </img> sunt satisfăcute), sunt acum utilizate în prezent în teoria numerelor analitice .

Exemple simple

Avem

Nu s-a putut interpreta (eroare de sintaxă): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mi> <math>\sin x=\Omega(1)\ (x\rightarrow\infty),} </mi><mo> $\sin x=\Omega (1)\ (x\rightarrow \infty ),$ </mo><mi> $\sin x=\Omega (1)\ (x\rightarrow \infty ),$ </mi><mo> $\sin x=\Omega (1)\ (x\rightarrow \infty ),$ </mo><mi mathvariant="normal"> $\sin x=\Omega (1)\ (x\rightarrow \infty ),$ </mi><mo stretchy="false"> $\sin x=\Omega (1)\ (x\rightarrow \infty ),$ </mo><mn> $\sin x=\Omega (1)\ (x\rightarrow \infty ),$ </mn><mo stretchy="false"> $\sin x=\Omega (1)\ (x\rightarrow \infty ),$ </mo><mo stretchy="false"> $\sin x=\Omega (1)\ (x\rightarrow \infty ),$ </mo><mi> $\sin x=\Omega (1)\ (x\rightarrow \infty ),$ </mi><mo stretchy="false"> $\sin x=\Omega (1)\ (x\rightarrow \infty ),$ </mo><mi mathvariant="normal"> $\sin x=\Omega (1)\ (x\rightarrow \infty ),$ </mi><mo stretchy="false"> $\sin x=\Omega (1)\ (x\rightarrow \infty ),$ </mo><mo> $\sin x=\Omega (1)\ (x\rightarrow \infty ),$ </mo></mstyle></mrow> </math>$\sin x=\Omega (1)\ (x\rightarrow \infty ),$ $\sin x=\Omega (1)\ (x\rightarrow \infty ),$ </img>

și mai precis

<mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mi> $\sin x=\Omega _{\pm }(1)\ (x\rightarrow \infty ).$ </mi><mo> $\sin x=\Omega _{\pm }(1)\ (x\rightarrow \infty ).$ </mo><mi> $\sin x=\Omega _{\pm }(1)\ (x\rightarrow \infty ).$ </mi><mo> $\sin x=\Omega _{\pm }(1)\ (x\rightarrow \infty ).$ </mo><msub><mi mathvariant="normal"> $\sin x=\Omega _{\pm }(1)\ (x\rightarrow \infty ).$ </mi><mrow class="MJX-TeXAtom-ORD"><mo> $\sin x=\Omega _{\pm }(1)\ (x\rightarrow \infty ).$ </mo></mrow></msub><mo stretchy="false"> $\sin x=\Omega _{\pm }(1)\ (x\rightarrow \infty ).$ </mo><mn> $\sin x=\Omega _{\pm }(1)\ (x\rightarrow \infty ).$ </mn><mo stretchy="false"> $\sin x=\Omega _{\pm }(1)\ (x\rightarrow \infty ).$ </mo><mo stretchy="false"> $\sin x=\Omega _{\pm }(1)\ (x\rightarrow \infty ).$ </mo><mi> $\sin x=\Omega _{\pm }(1)\ (x\rightarrow \infty ).$ </mi><mo stretchy="false"> $\sin x=\Omega _{\pm }(1)\ (x\rightarrow \infty ).$ </mo><mi mathvariant="normal"> $\sin x=\Omega _{\pm }(1)\ (x\rightarrow \infty ).$ </mi><mo stretchy="false"> $\sin x=\Omega _{\pm }(1)\ (x\rightarrow \infty ).$ </mo><mo> $\sin x=\Omega _{\pm }(1)\ (x\rightarrow \infty ).$ </mo></mstyle></mrow> $\sin x=\Omega _{\pm }(1)\ (x\rightarrow \infty ).$ ${\displaystyle }$$\sin x=\Omega _{\pm }(1)\ (x\rightarrow \infty ).$ $\sin x=\Omega _{\pm }(1)\ (x\rightarrow \infty ).$ </img>

Avem

Nu s-a putut interpreta (eroare de sintaxă): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mi> <math>\sin x+1=\Omega(1)\ (x\rightarrow\infty),} </mi><mo> $\sin x+1=\Omega (1)\ (x\rightarrow \infty ),$ </mo><mi> $\sin x+1=\Omega (1)\ (x\rightarrow \infty ),$ </mi><mo> $\sin x+1=\Omega (1)\ (x\rightarrow \infty ),$ </mo><mn> $\sin x+1=\Omega (1)\ (x\rightarrow \infty ),$ </mn><mo> $\sin x+1=\Omega (1)\ (x\rightarrow \infty ),$ </mo><mi mathvariant="normal"> $\sin x+1=\Omega (1)\ (x\rightarrow \infty ),$ </mi><mo stretchy="false"> $\sin x+1=\Omega (1)\ (x\rightarrow \infty ),$ </mo><mn> $\sin x+1=\Omega (1)\ (x\rightarrow \infty ),$ </mn><mo stretchy="false"> $\sin x+1=\Omega (1)\ (x\rightarrow \infty ),$ </mo><mo stretchy="false"> $\sin x+1=\Omega (1)\ (x\rightarrow \infty ),$ </mo><mi> $\sin x+1=\Omega (1)\ (x\rightarrow \infty ),$ </mi><mo stretchy="false"> $\sin x+1=\Omega (1)\ (x\rightarrow \infty ),$ </mo><mi mathvariant="normal"> $\sin x+1=\Omega (1)\ (x\rightarrow \infty ),$ </mi><mo stretchy="false"> $\sin x+1=\Omega (1)\ (x\rightarrow \infty ),$ </mo><mo> $\sin x+1=\Omega (1)\ (x\rightarrow \infty ),$ </mo></mstyle></mrow> </math>$\sin x+1=\Omega (1)\ (x\rightarrow \infty ),$ $\sin x+1=\Omega (1)\ (x\rightarrow \infty ),$ </img>

și mai precis

Nu s-a putut interpreta (eroare de sintaxă): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mi> <math>\sin x+1=\Omega_+(1)\ (x\rightarrow\infty);} </mi><mo> $\sin x+1=\Omega _{+}(1)\ (x\rightarrow \infty );$ </mo><mi> $\sin x+1=\Omega _{+}(1)\ (x\rightarrow \infty );$ </mi><mo> $\sin x+1=\Omega _{+}(1)\ (x\rightarrow \infty );$ </mo><mn> $\sin x+1=\Omega _{+}(1)\ (x\rightarrow \infty );$ </mn><mo> $\sin x+1=\Omega _{+}(1)\ (x\rightarrow \infty );$ </mo><msub><mi mathvariant="normal"> $\sin x+1=\Omega _{+}(1)\ (x\rightarrow \infty );$ </mi><mrow class="MJX-TeXAtom-ORD"><mo> $\sin x+1=\Omega _{+}(1)\ (x\rightarrow \infty );$ </mo></mrow></msub><mo stretchy="false"> $\sin x+1=\Omega _{+}(1)\ (x\rightarrow \infty );$ </mo><mn> $\sin x+1=\Omega _{+}(1)\ (x\rightarrow \infty );$ </mn><mo stretchy="false"> $\sin x+1=\Omega _{+}(1)\ (x\rightarrow \infty );$ </mo><mo stretchy="false"> $\sin x+1=\Omega _{+}(1)\ (x\rightarrow \infty );$ </mo><mi> $\sin x+1=\Omega _{+}(1)\ (x\rightarrow \infty );$ </mi><mo stretchy="false"> $\sin x+1=\Omega _{+}(1)\ (x\rightarrow \infty );$ </mo><mi mathvariant="normal"> $\sin x+1=\Omega _{+}(1)\ (x\rightarrow \infty );$ </mi><mo stretchy="false"> $\sin x+1=\Omega _{+}(1)\ (x\rightarrow \infty );$ </mo><mo> $\sin x+1=\Omega _{+}(1)\ (x\rightarrow \infty );$ </mo></mstyle></mrow> </math>$\sin x+1=\Omega _{+}(1)\ (x\rightarrow \infty );$ $\sin x+1=\Omega _{+}(1)\ (x\rightarrow \infty );$ </img>

dar

<mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mi> $\sin x+1\not =\Omega _{-}(1)\ (x\rightarrow \infty ).$ </mi><mo> $\sin x+1\not =\Omega _{-}(1)\ (x\rightarrow \infty ).$ </mo><mi> $\sin x+1\not =\Omega _{-}(1)\ (x\rightarrow \infty ).$ </mi><mo> $\sin x+1\not =\Omega _{-}(1)\ (x\rightarrow \infty ).$ </mo><mn> $\sin x+1\not =\Omega _{-}(1)\ (x\rightarrow \infty ).$ </mn><mo> $\sin x+1\not =\Omega _{-}(1)\ (x\rightarrow \infty ).$ </mo><msub><mi mathvariant="normal"> $\sin x+1\not =\Omega _{-}(1)\ (x\rightarrow \infty ).$ </mi><mrow class="MJX-TeXAtom-ORD"><mo> $\sin x+1\not =\Omega _{-}(1)\ (x\rightarrow \infty ).$ </mo></mrow></msub><mo stretchy="false"> $\sin x+1\not =\Omega _{-}(1)\ (x\rightarrow \infty ).$ </mo><mn> $\sin x+1\not =\Omega _{-}(1)\ (x\rightarrow \infty ).$ </mn><mo stretchy="false"> $\sin x+1\not =\Omega _{-}(1)\ (x\rightarrow \infty ).$ </mo><mo stretchy="false"> $\sin x+1\not =\Omega _{-}(1)\ (x\rightarrow \infty ).$ </mo><mi> $\sin x+1\not =\Omega _{-}(1)\ (x\rightarrow \infty ).$ </mi><mo stretchy="false"> $\sin x+1\not =\Omega _{-}(1)\ (x\rightarrow \infty ).$ </mo><mi mathvariant="normal"> $\sin x+1\not =\Omega _{-}(1)\ (x\rightarrow \infty ).$ </mi><mo stretchy="false"> $\sin x+1\not =\Omega _{-}(1)\ (x\rightarrow \infty ).$ </mo><mo> $\sin x+1\not =\Omega _{-}(1)\ (x\rightarrow \infty ).$ </mo></mstyle></mrow> $\sin x+1\not =\Omega _{-}(1)\ (x\rightarrow \infty ).$ ${\displaystyle }$$\sin x+1\not =\Omega _{-}(1)\ (x\rightarrow \infty ).$ $\sin x+1\not =\Omega _{-}(1)\ (x\rightarrow \infty ).$ </img>

Definiția Knuth

În 1976, Donald Knuth a publicat o lucrare pentru a justifica utilizarea simbolului Nu s-a putut interpreta (eroare de sintaxă): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mi mathvariant="normal"> <math>\Omega} </mi></mstyle></mrow> </math>$\Omega$ $\Omega$ </img> 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

Nu s-a putut interpreta (eroare de sintaxă): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mi> <math>f(x)=\Omega(g(x))\Leftrightarrow g(x)=O(f(x))} </mi><mo stretchy="false"> $f(x)=\Omega (g(x))\Leftrightarrow g(x)=O(f(x))$ </mo><mi> $f(x)=\Omega (g(x))\Leftrightarrow g(x)=O(f(x))$ </mi><mo stretchy="false"> $f(x)=\Omega (g(x))\Leftrightarrow g(x)=O(f(x))$ </mo><mo> $f(x)=\Omega (g(x))\Leftrightarrow g(x)=O(f(x))$ </mo><mi mathvariant="normal"> $f(x)=\Omega (g(x))\Leftrightarrow g(x)=O(f(x))$ </mi><mo stretchy="false"> $f(x)=\Omega (g(x))\Leftrightarrow g(x)=O(f(x))$ </mo><mi> $f(x)=\Omega (g(x))\Leftrightarrow g(x)=O(f(x))$ </mi><mo stretchy="false"> $f(x)=\Omega (g(x))\Leftrightarrow g(x)=O(f(x))$ </mo><mi> $f(x)=\Omega (g(x))\Leftrightarrow g(x)=O(f(x))$ </mi><mo stretchy="false"> $f(x)=\Omega (g(x))\Leftrightarrow g(x)=O(f(x))$ </mo><mo stretchy="false"> $f(x)=\Omega (g(x))\Leftrightarrow g(x)=O(f(x))$ </mo><mo stretchy="false"> $f(x)=\Omega (g(x))\Leftrightarrow g(x)=O(f(x))$ </mo><mi> $f(x)=\Omega (g(x))\Leftrightarrow g(x)=O(f(x))$ </mi><mo stretchy="false"> $f(x)=\Omega (g(x))\Leftrightarrow g(x)=O(f(x))$ </mo><mi> $f(x)=\Omega (g(x))\Leftrightarrow g(x)=O(f(x))$ </mi><mo stretchy="false"> $f(x)=\Omega (g(x))\Leftrightarrow g(x)=O(f(x))$ </mo><mo> $f(x)=\Omega (g(x))\Leftrightarrow g(x)=O(f(x))$ </mo><mi> $f(x)=\Omega (g(x))\Leftrightarrow g(x)=O(f(x))$ </mi><mo stretchy="false"> $f(x)=\Omega (g(x))\Leftrightarrow g(x)=O(f(x))$ </mo><mi> $f(x)=\Omega (g(x))\Leftrightarrow g(x)=O(f(x))$ </mi><mo stretchy="false"> $f(x)=\Omega (g(x))\Leftrightarrow g(x)=O(f(x))$ </mo><mi> $f(x)=\Omega (g(x))\Leftrightarrow g(x)=O(f(x))$ </mi><mo stretchy="false"> $f(x)=\Omega (g(x))\Leftrightarrow g(x)=O(f(x))$ </mo><mo stretchy="false"> $f(x)=\Omega (g(x))\Leftrightarrow g(x)=O(f(x))$ </mo></mstyle></mrow> </math>$f(x)=\Omega (g(x))\Leftrightarrow g(x)=O(f(x))$ $f(x)=\Omega (g(x))\Leftrightarrow g(x)=O(f(x))$ </img>

cu comentariul: „Deși am schimbat definiția dată de Hardy și a Littlewood pentru Nu s-a putut interpreta (eroare de sintaxă): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mi mathvariant="normal"> <math>\Omega} </mi></mstyle></mrow> </math>$\Omega$ $\Omega$ </img> , 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.”

Familia de notații Bachmann-Landau

Notația	Nume	Descriere	Definiție formală	Limit Definition
$f(n)=o(g(n))$	Small O; Small Oh	f este dominată de g asimptotic	$\forall k>0\;\exists n_{0}\;\forall n>n_{0}\;|f(n)|<k\cdot g(n)$	$\lim _{n\to \infty }{\frac {f(n)}{g(n)}}=0$
$f(n)=O(g(n))$	Big O; Big Oh; Big Omicron	$|f|$ este mărginită superior de g (până la un factor constant) asimptotic	$\exists k>0\;\exists n_{0}\;\forall n>n_{0}\;|f(n)|\leq k\cdot g(n)$	$\limsup _{n\to \infty }{\frac {\left|f(n)\right|}{g(n)}}<\infty$
$f(n)=\Theta (g(n))$	Big Theta	f este mărginită atât superior cât și inferior de g asimptotic	$\exists k_{1}>0\;\exists k_{2}>0\;\exists n_{0}\;\forall n>n_{0}$$k_{1}\cdot g(n)\leq f(n)\leq k_{2}\cdot g(n)$	$f(n)=O(g(n))$ and $f(n)=\Omega (g(n))$ (Knuth version)
$f(n)\sim g(n)$	De ordinul lui	f este egal cu g asimptotic	$\forall \varepsilon >0\;\exists n_{0}\;\forall n>n_{0}\;\left|{f(n) \over g(n)}-1\right|<\varepsilon$	$\lim _{n\to \infty }{f(n) \over g(n)}=1$
$f(n)=\Omega (g(n))$	Big Omega în teoria numerelor (Hardy–Littlewood)	$|f|$ nu este dominată de g asimptotic	$\exists k>0\;\forall n_{0}\;\exists n>n_{0}\;|f(n)|\geq k\cdot g(n)$	$\limsup _{n\to \infty }\left|{\frac {f(n)}{g(n)}}\right|>0$
$f(n)=\Omega (g(n))$	Big Omega în teoria complexității (Knuth)	f este mărginit inferior de g asimptotic	$\exists k>0\;\exists n_{0}\;\forall n>n_{0}\;f(n)\geq k\cdot g(n)$	$\liminf _{n\to \infty }{\frac {f(n)}{g(n)}}>0$
$f(n)=\omega (g(n))$	Small Omega	f domină g asimptotic	$\forall k>0\;\exists n_{0}\;\forall n>n_{0}\ |f(n)|>k\cdot |g(n)|$	$\lim _{n\to \infty }\left|{\frac {f(n)}{g(n)}}\right|=\infty$

Definițiile limitelor presupun Nu s-a putut interpreta (eroare de sintaxă): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mi> <math>g(n) \neq 0} </mi><mo stretchy="false"> $g(n)\neq 0$ </mo><mi> $g(n)\neq 0$ </mi><mo stretchy="false"> $g(n)\neq 0$ </mo><mo> $g(n)\neq 0$ </mo><mn> $g(n)\neq 0$ </mn></mstyle></mrow> </math>$g(n)\neq 0$ $g(n)\neq 0$ </img> pentru 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ă (versiunea Hardy-Littlewood a lui Ω nu corespunde însă unei astfel de descrieri).

Informatica folosește Big O, bog Theta Θ, little o, omega ω și notația Big Omega Ω a lui Knuth. 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 Nu s-a putut interpreta (eroare de sintaxă): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mo> <math>\sim} </mo></mstyle></mrow> </math>$\sim$ $\sim$ </img> . Notația small omega ω nu este utilizată la fel de des în analiză.

Utilizați î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ă unde notația Theta Θ ar putea fi mai potrivită într-un anumit context. De exemplu, atunci când se analizează o funcție T(n) = 73n³ + 22n² + 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).

1. T(n) = O(n¹⁰⁰)
2. T(n) = O(n³)
3. T(n) = Θ(n³)

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

1. T(n) crește asymptotic nu mai repede decât n¹⁰⁰
2. T(n) crește asymptotic nu mai repede decât n³
3. T(n) crește asimptotic la fel de repede ca n³.

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ă T(n) reprezintă timpul de funcționare a algoritmului nou dezvoltat pentru dimensiunea de intrare 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 Introducere în algoritmi, Cormen, Leiserson, Rivest și Stein iau în considerare mulțimea funcțiilor f care satisfac

<mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mi> $f(n)=O(g(n))\ (n\rightarrow \infty ).$ </mi><mo stretchy="false"> $f(n)=O(g(n))\ (n\rightarrow \infty ).$ </mo><mi> $f(n)=O(g(n))\ (n\rightarrow \infty ).$ </mi><mo stretchy="false"> $f(n)=O(g(n))\ (n\rightarrow \infty ).$ </mo><mo> $f(n)=O(g(n))\ (n\rightarrow \infty ).$ </mo><mi> $f(n)=O(g(n))\ (n\rightarrow \infty ).$ </mi><mo stretchy="false"> $f(n)=O(g(n))\ (n\rightarrow \infty ).$ </mo><mi> $f(n)=O(g(n))\ (n\rightarrow \infty ).$ </mi><mo stretchy="false"> $f(n)=O(g(n))\ (n\rightarrow \infty ).$ </mo><mi> $f(n)=O(g(n))\ (n\rightarrow \infty ).$ </mi><mo stretchy="false"> $f(n)=O(g(n))\ (n\rightarrow \infty ).$ </mo><mo stretchy="false"> $f(n)=O(g(n))\ (n\rightarrow \infty ).$ </mo><mo stretchy="false"> $f(n)=O(g(n))\ (n\rightarrow \infty ).$ </mo><mi> $f(n)=O(g(n))\ (n\rightarrow \infty ).$ </mi><mo stretchy="false"> $f(n)=O(g(n))\ (n\rightarrow \infty ).$ </mo><mi mathvariant="normal"> $f(n)=O(g(n))\ (n\rightarrow \infty ).$ </mi><mo stretchy="false"> $f(n)=O(g(n))\ (n\rightarrow \infty ).$ </mo><mo> $f(n)=O(g(n))\ (n\rightarrow \infty ).$ </mo></mstyle></mrow> $f(n)=O(g(n))\ (n\rightarrow \infty ).$ ${\displaystyle }$$f(n)=O(g(n))\ (n\rightarrow \infty ).$ $f(n)=O(g(n))\ (n\rightarrow \infty ).$ </img>

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

Nu s-a putut interpreta (eroare de sintaxă): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mi> <math>O(g) = \{ f :} </mi><mo stretchy="false"> $O(g)=\{f:$ </mo><mi> $O(g)=\{f:$ </mi><mo stretchy="false"> $O(g)=\{f:$ </mo><mo> $O(g)=\{f:$ </mo><mo fence="false" stretchy="false"> $O(g)=\{f:$ </mo><mi> $O(g)=\{f:$ </mi><mo> $O(g)=\{f:$ </mo></mstyle></mrow> </math>$O(g)=\{f:$ $O(g)=\{f:$ </img> există constante pozitive c și Nu s-a putut interpreta (eroare de sintaxă): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><msub><mi> <math>n_0} </mi><mrow class="MJX-TeXAtom-ORD"><mn> $n_{0}$ </mn></mrow></msub></mstyle></mrow> </math>$n_{0}$ $n_{0}$ </img> astfel încât Nu s-a putut interpreta (eroare de sintaxă): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mn> <math>0 \le f(n) \le cg(n)} </mn><mo> $0\leq f(n)\leq cg(n)$ </mo><mi> $0\leq f(n)\leq cg(n)$ </mi><mo stretchy="false"> $0\leq f(n)\leq cg(n)$ </mo><mi> $0\leq f(n)\leq cg(n)$ </mi><mo stretchy="false"> $0\leq f(n)\leq cg(n)$ </mo><mo> $0\leq f(n)\leq cg(n)$ </mo><mi> $0\leq f(n)\leq cg(n)$ </mi><mi> $0\leq f(n)\leq cg(n)$ </mi><mo stretchy="false"> $0\leq f(n)\leq cg(n)$ </mo><mi> $0\leq f(n)\leq cg(n)$ </mi><mo stretchy="false"> $0\leq f(n)\leq cg(n)$ </mo></mstyle></mrow> </math>$0\leq f(n)\leq cg(n)$ $0\leq f(n)\leq cg(n)$ </img> pentru toți Nu s-a putut interpreta (eroare de sintaxă): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mi> <math>n \ge n_0 \}} </mi><mo> $n\geq n_{0}\}$ </mo><msub><mi> $n\geq n_{0}\}$ </mi><mrow class="MJX-TeXAtom-ORD"><mn> $n\geq n_{0}\}$ </mn></mrow></msub><mo fence="false" stretchy="false"> $n\geq n_{0}\}$ </mo></mstyle></mrow> </math>$n\geq n_{0}\}$ $n\geq n_{0}\}$ </img> .

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. Într-o ecuație sau inegalitate, folosirea unei notații asimptotice reprezintă o funcție anonimă din mulțimea O(g), care elimină termenii de ordin inferior și ajută la reducerea aglomerării inutile în ecuații, de exemplu:

<mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mn> $2n^{2}+3n+1=2n^{2}+O(n).$ </mn><msup><mi> $2n^{2}+3n+1=2n^{2}+O(n).$ </mi><mrow class="MJX-TeXAtom-ORD"><mn> $2n^{2}+3n+1=2n^{2}+O(n).$ </mn></mrow></msup><mo> $2n^{2}+3n+1=2n^{2}+O(n).$ </mo><mn> $2n^{2}+3n+1=2n^{2}+O(n).$ </mn><mi> $2n^{2}+3n+1=2n^{2}+O(n).$ </mi><mo> $2n^{2}+3n+1=2n^{2}+O(n).$ </mo><mn> $2n^{2}+3n+1=2n^{2}+O(n).$ </mn><mo> $2n^{2}+3n+1=2n^{2}+O(n).$ </mo><mn> $2n^{2}+3n+1=2n^{2}+O(n).$ </mn><msup><mi> $2n^{2}+3n+1=2n^{2}+O(n).$ </mi><mrow class="MJX-TeXAtom-ORD"><mn> $2n^{2}+3n+1=2n^{2}+O(n).$ </mn></mrow></msup><mo> $2n^{2}+3n+1=2n^{2}+O(n).$ </mo><mi> $2n^{2}+3n+1=2n^{2}+O(n).$ </mi><mo stretchy="false"> $2n^{2}+3n+1=2n^{2}+O(n).$ </mo><mi> $2n^{2}+3n+1=2n^{2}+O(n).$ </mi><mo stretchy="false"> $2n^{2}+3n+1=2n^{2}+O(n).$ </mo><mo> $2n^{2}+3n+1=2n^{2}+O(n).$ </mo></mstyle></mrow> $2n^{2}+3n+1=2n^{2}+O(n).$ ${\displaystyle }$$2n^{2}+3n+1=2n^{2}+O(n).$ $2n^{2}+3n+1=2n^{2}+O(n).$ </img>

Extensii la notațiile Bachmann-Landau

O altă notație folosită uneori în domeniul informaticii este Õ (citiți soft-O): f(n) = Õ(g(n)) este o prescurtare pentru f(n) = O(g(n) log k g(n)) pentru un anume 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 log^k n este întotdeauna o(n^ε) pentru orice constantă k și orice ε > 0).

De asemenea, notația L, definită ca

Nu s-a putut interpreta (MathML cu fallback pe SVG sau PNG (recomandat pentru browserele moderne și uneltele de accesibilitate): Răspuns incorect („Math extension cannot connect to Restbase.”) de la serverul „http://localhost:6011/ro.wikipedia.org/v1/”:): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><msub><mi> <math>L_n[\alpha,c]=e^{(c+o(1))(\ln n)^\alpha(\ln\ln n)^{1-\alpha}}} </mi><mrow class="MJX-TeXAtom-ORD"><mi> $L_{n}[\alpha ,c]=e^{(c+o(1))(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }}$ </mi></mrow></msub><mo stretchy="false"> $L_{n}[\alpha ,c]=e^{(c+o(1))(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }}$ </mo><mi> $L_{n}[\alpha ,c]=e^{(c+o(1))(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }}$ </mi><mo> $L_{n}[\alpha ,c]=e^{(c+o(1))(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }}$ </mo><mi> $L_{n}[\alpha ,c]=e^{(c+o(1))(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }}$ </mi><mo stretchy="false"> $L_{n}[\alpha ,c]=e^{(c+o(1))(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }}$ </mo><mo> $L_{n}[\alpha ,c]=e^{(c+o(1))(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }}$ </mo><msup><mi> $L_{n}[\alpha ,c]=e^{(c+o(1))(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }}$ </mi><mrow class="MJX-TeXAtom-ORD"><mo stretchy="false"> $L_{n}[\alpha ,c]=e^{(c+o(1))(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }}$ </mo><mi> $L_{n}[\alpha ,c]=e^{(c+o(1))(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }}$ </mi><mo> $L_{n}[\alpha ,c]=e^{(c+o(1))(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }}$ </mo><mi> $L_{n}[\alpha ,c]=e^{(c+o(1))(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }}$ </mi><mo stretchy="false"> $L_{n}[\alpha ,c]=e^{(c+o(1))(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }}$ </mo><mn> $L_{n}[\alpha ,c]=e^{(c+o(1))(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }}$ </mn><mo stretchy="false"> $L_{n}[\alpha ,c]=e^{(c+o(1))(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }}$ </mo><mo stretchy="false"> $L_{n}[\alpha ,c]=e^{(c+o(1))(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }}$ </mo><mo stretchy="false"> $L_{n}[\alpha ,c]=e^{(c+o(1))(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }}$ </mo><mi> $L_{n}[\alpha ,c]=e^{(c+o(1))(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }}$ </mi><mo> $L_{n}[\alpha ,c]=e^{(c+o(1))(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }}$ </mo><mi> $L_{n}[\alpha ,c]=e^{(c+o(1))(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }}$ </mi><msup><mo stretchy="false"> $L_{n}[\alpha ,c]=e^{(c+o(1))(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }}$ </mo><mrow class="MJX-TeXAtom-ORD"><mi> $L_{n}[\alpha ,c]=e^{(c+o(1))(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }}$ </mi></mrow></msup><mo stretchy="false"> $L_{n}[\alpha ,c]=e^{(c+o(1))(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }}$ </mo><mi> $L_{n}[\alpha ,c]=e^{(c+o(1))(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }}$ </mi><mo> $L_{n}[\alpha ,c]=e^{(c+o(1))(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }}$ </mo><mi> $L_{n}[\alpha ,c]=e^{(c+o(1))(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }}$ </mi><mo> $L_{n}[\alpha ,c]=e^{(c+o(1))(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }}$ </mo><mi> $L_{n}[\alpha ,c]=e^{(c+o(1))(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }}$ </mi><msup><mo stretchy="false"> $L_{n}[\alpha ,c]=e^{(c+o(1))(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }}$ </mo><mrow class="MJX-TeXAtom-ORD"><mn> $L_{n}[\alpha ,c]=e^{(c+o(1))(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }}$ </mn><mo> $L_{n}[\alpha ,c]=e^{(c+o(1))(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }}$ </mo><mi> $L_{n}[\alpha ,c]=e^{(c+o(1))(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }}$ </mi></mrow></msup></mrow></msup></mstyle></mrow> </math>$L_{n}[\alpha ,c]=e^{(c+o(1))(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }}$ $L_{n}[\alpha ,c]=e^{(c+o(1))(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }}$ </img>

este convenabilă pentru funcțiile care sunt între polinomială și exponențială în termeni de Nu s-a putut interpreta (eroare de sintaxă): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mi> <math>\ln n} </mi><mo> $\ln n$ </mo><mi> $\ln n$ </mi></mstyle></mrow> </math>$\ln n$ $\ln n$ </img> .

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 f și g nu este nevoie săi aibă valori în același spațiu. O generalizare a funcțiilor g cu valori în orice grup topologic este de asemenea posibilă. „Procesul de limitare” x→x₀ poate fi și el generalizat prin introducerea unei baze de filtrare arbitrare, adică a rețelelor direcționate f și g. Notația o poate fi folosită pentru a defini derivate și diferențiabilitatea în spații destul de generale, precum și echivalența (asimptotică) a funcțiilor,

Nu s-a putut interpreta (eroare de sintaxă): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mi> <math> f\sim g \iff (f-g) \in o(g) } </mi><mo> $f\sim g\iff (f-g)\in o(g)$ </mo><mi> $f\sim g\iff (f-g)\in o(g)$ </mi><mo stretchy="false"> $f\sim g\iff (f-g)\in o(g)$ </mo><mo stretchy="false"> $f\sim g\iff (f-g)\in o(g)$ </mo><mi> $f\sim g\iff (f-g)\in o(g)$ </mi><mo> $f\sim g\iff (f-g)\in o(g)$ </mo><mi> $f\sim g\iff (f-g)\in o(g)$ </mi><mo stretchy="false"> $f\sim g\iff (f-g)\in o(g)$ </mo><mo> $f\sim g\iff (f-g)\in o(g)$ </mo><mi> $f\sim g\iff (f-g)\in o(g)$ </mi><mo stretchy="false"> $f\sim g\iff (f-g)\in o(g)$ </mo><mi> $f\sim g\iff (f-g)\in o(g)$ </mi><mo stretchy="false"> $f\sim g\iff (f-g)\in o(g)$ </mo></mstyle></mrow> </math>$f\sim g\iff (f-g)\in o(g)$ $f\sim g\iff (f-g)\in o(g)$ </img>

care este o relație de echivalență și o noțiune mai restrictivă decât relația „f este Θ(g)” de mai sus. (Se reduce la lim f/g = 1 dacă f și g sunt funcții cu valoare reală pozitivă.) De exemplu, 2x este Θ(x), dar 2x - x nu este 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 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. Teoreticianul numerelor Edmund Landau a adoptat-o și, astfel, a fost inspirat să introducă în 1909 notația o; aici ambele sunt numite acum simboluri Landau. Aceste notații au fost folosite în matematica aplicată în anii 1950 pentru analiza asimptotică. Simbolul Nu s-a putut interpreta (eroare de sintaxă): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mi mathvariant="normal"> <math>\Omega} </mi></mstyle></mrow> </math>$\Omega$ $\Omega$ </img> (în sensul „nu este o de”) a fost introdus în 1914 de Hardy și Littlewood. Hardy și Littlewood au introdus, de asemenea, în 1918 simbolurile Nu s-a putut interpreta (eroare de sintaxă): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><msub><mi mathvariant="normal"> <math>\Omega_R} </mi><mrow class="MJX-TeXAtom-ORD"><mi> $\Omega _{R}$ </mi></mrow></msub></mstyle></mrow> </math>$\Omega _{R}$ $\Omega _{R}$ </img> („dreapta”) și Nu s-a putut interpreta (eroare de sintaxă): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><msub><mi mathvariant="normal"> <math>\Omega_L} </mi><mrow class="MJX-TeXAtom-ORD"><mi> $\Omega _{L}$ </mi></mrow></msub></mstyle></mrow> </math>$\Omega _{L}$ $\Omega _{L}$ </img> („stânga”), precursori ai simbolurilor moderne Nu s-a putut interpreta (eroare de sintaxă): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><msub><mi mathvariant="normal"> <math>\Omega_+} </mi><mrow class="MJX-TeXAtom-ORD"><mo> $\Omega _{+}$ </mo></mrow></msub></mstyle></mrow> </math>$\Omega _{+}$ $\Omega _{+}$ </img> („nu este mai mică decât small o de”) și Nu s-a putut interpreta (eroare de sintaxă): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><msub><mi mathvariant="normal"> <math>\Omega_-} </mi><mrow class="MJX-TeXAtom-ORD"><mo> $\Omega _{-}$ </mo></mrow></msub></mstyle></mrow> </math>$\Omega _{-}$ $\Omega _{-}$ </img> („nu este mai mare decât small o de”). Astfel, simbolurile Omega (cu semnificațiile lor originale) sunt uneori denumite și „simboluri Landau”. Această notație Nu s-a putut interpreta (eroare de sintaxă): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mi mathvariant="normal"> <math>\Omega} </mi></mstyle></mrow> </math>$\Omega$ $\Omega$ </img> a devenit frecvent folosită în teoria numerelor cel puțin din anii 1950. În anii 1970, Big O a fost popularizată în domeniul informaticii de către Donald Knuth, care a introdus notația aferentă Theta și a propus o altă definiție pentru notația Omega.

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

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

Nu s-a putut interpreta (eroare de sintaxă): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mi> <math> f \preccurlyeq g\iff f \in O(g) } </mi><mo> $f\preccurlyeq g\iff f\in O(g)$ </mo><mi> $f\preccurlyeq g\iff f\in O(g)$ </mi><mo stretchy="false"> $f\preccurlyeq g\iff f\in O(g)$ </mo><mi> $f\preccurlyeq g\iff f\in O(g)$ </mi><mo> $f\preccurlyeq g\iff f\in O(g)$ </mo><mi> $f\preccurlyeq g\iff f\in O(g)$ </mi><mo stretchy="false"> $f\preccurlyeq g\iff f\in O(g)$ </mo><mi> $f\preccurlyeq g\iff f\in O(g)$ </mi><mo stretchy="false"> $f\preccurlyeq g\iff f\in O(g)$ </mo></mstyle></mrow> </math>$f\preccurlyeq g\iff f\in O(g)$ $f\preccurlyeq g\iff f\in O(g)$ </img>   și   Nu s-a putut interpreta (eroare de sintaxă): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mi> <math> f\prec g\iff f\in o(g); } </mi><mo> $f\prec g\iff f\in o(g);$ </mo><mi> $f\prec g\iff f\in o(g);$ </mi><mo stretchy="false"> $f\prec g\iff f\in o(g);$ </mo><mi> $f\prec g\iff f\in o(g);$ </mi><mo> $f\prec g\iff f\in o(g);$ </mo><mi> $f\prec g\iff f\in o(g);$ </mi><mo stretchy="false"> $f\prec g\iff f\in o(g);$ </mo><mi> $f\prec g\iff f\in o(g);$ </mi><mo stretchy="false"> $f\prec g\iff f\in o(g);$ </mo><mo> $f\prec g\iff f\in o(g);$ </mo></mstyle></mrow> </math>$f\prec g\iff f\in o(g);$ $f\prec g\iff f\in o(g);$ </img>

(Hardy însă nu a definit niciodată și nu a folosit notația Nu s-a putut interpreta (eroare de sintaxă): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mo> <math>\prec\!\!\prec} </mo><mo> $\prec \!\!\prec$ </mo></mstyle></mrow> </math>$\prec \!\!\prec$ $\prec \!\!\prec$ </img> , nici Nu s-a putut interpreta (eroare de sintaxă): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mo> <math>\ll} </mo></mstyle></mrow> </math>$\ll$ $\ll$ </img> , așa cum s-a afirmat uneori). De asemenea, Hardy a introdus simbolurile Nu s-a putut interpreta (eroare de sintaxă): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mo> <math>\preccurlyeq } </mo></mstyle></mrow> </math>$\preccurlyeq$ $\preccurlyeq$ </img> și Nu s-a putut interpreta (eroare de sintaxă): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mo> <math>\prec } </mo></mstyle></mrow> </math>$\prec$ $\prec$ </img> (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 cele aproape 400 de lucrări și cărți rămase, el folosește consistent simbolurile Landau O și o.

Notația lui Hardy nu mai este folosită. Pe de altă parte, în 1930, teoreticianului rus al numerelor Ivan Matveievici Vinogradov a introdus notația lui, Nu s-a putut interpreta (eroare de sintaxă): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mo> <math>\ll} </mo></mstyle></mrow> </math>$\ll$ $\ll$ </img> , care este folosită din ce în ce mai mult în teoria numerelor în locul notației Nu s-a putut interpreta (eroare de sintaxă): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mi> <math>O} </mi></mstyle></mrow> </math>$O$ $O$ </img> . Avem

Nu s-a putut interpreta (eroare de sintaxă): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mi> <math> f\ll g \iff f \in O(g), } </mi><mo> $f\ll g\iff f\in O(g),$ </mo><mi> $f\ll g\iff f\in O(g),$ </mi><mo stretchy="false"> $f\ll g\iff f\in O(g),$ </mo><mi> $f\ll g\iff f\in O(g),$ </mi><mo> $f\ll g\iff f\in O(g),$ </mo><mi> $f\ll g\iff f\in O(g),$ </mi><mo stretchy="false"> $f\ll g\iff f\in O(g),$ </mo><mi> $f\ll g\iff f\in O(g),$ </mi><mo stretchy="false"> $f\ll g\iff f\in O(g),$ </mo><mo> $f\ll g\iff f\in O(g),$ </mo></mstyle></mrow> </math>$f\ll g\iff f\in O(g),$ $f\ll g\iff f\in O(g),$ </img>

ș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 probabil în legătură cu definiția sa a simbolului Omega. Nu se folosește cifra zero.

Lectură suplimentară

• Hardy, G. H. (1910). Orders of Infinity: The 'Infinitärcalcül' of Paul du Bois-Reymond. Cambridge University Press. 
• Knuth, Donald (1997). „1.2.11: Asymptotic Representations”. Fundamental Algorithms. The Art of Computer Programming. 1 (ed. 3rd). Addison–Wesley. ISBN 978-0-201-89683-1. 
• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). „3.1: Asymptotic notation”. Introduction to Algorithms (ed. 2nd). MIT Press and McGraw–Hill. ISBN 978-0-262-03293-3. 
• Sipser, Michael (1997). Introduction to the Theory of Computation. PWS Publishing. pp. 226–228. ISBN 978-0-534-94728-6. 
• Avigad, Jeremy; Donnelly, Kevin (2004). Formalizing O notation in Isabelle/HOL (PDF). International Joint Conference on Automated Reasoning. doi:10.1007/978-3-540-25984-8_27. 
• Black, Paul E. (11 martie 2005). Black, Paul E., ed. „big-O notation”. Dictionary of Algorithms and Data Structures. U.S. National Institute of Standards and Technology. Accesat în 16 decembrie 2006. 
• Black, Paul E. (17 decembrie 2004). Black, Paul E., ed. „little-o notation”. Dictionary of Algorithms and Data Structures. U.S. National Institute of Standards and Technology. Accesat în 16 decembrie 2006. 
• Black, Paul E. (17 decembrie 2004). Black, Paul E., ed. „Ω”. Dictionary of Algorithms and Data Structures. U.S. National Institute of Standards and Technology. Accesat în 16 decembrie 2006. 
• Black, Paul E. (17 decembrie 2004). Black, Paul E., ed. „ω”. Dictionary of Algorithms and Data Structures. U.S. National Institute of Standards and Technology. Accesat în 16 decembrie 2006. 
• Black, Paul E. (17 decembrie 2004). Black, Paul E., ed. „Θ”. Dictionary of Algorithms and Data Structures. U.S. National Institute of Standards and Technology. Accesat în 16 decembrie 2006. 

Legături externe

• Creșterea șirurilor - OEIS (Online Encyclopedia of Integer Sequences) Wiki
• Introducere în notații asimptotice
• Simboluri Landau
• Notația Big-O - la ce servește
• Big O Notation explicată în engleză simplă