Mostrar código-fonte de Grande-O

[[Imagem:Big-O-notation.png|400px|thumb|Exemplo da notação O-grande: {{color|#ff0000|''f''(''x'')}} ∈ O({{color|#0000ff|''g''(''x'')}}) de forma que existem ''c''&nbsp;>&nbsp;0 (e.g., ''c''&nbsp;=&nbsp;1) e ''x''<sub>0</sub> (e.g., ''x''<sub>0</sub>&nbsp;=&nbsp;5) tal que {{color|#ff0000|''f''(''x'')}}&nbsp;≤&nbsp;''c''{{color|#0000ff|''g''(''x'')}} sempre que ''x''&nbsp;≥&nbsp;''x''<sub>0</sub>.]]
Na [[matemática]], a '''notação O-grande''' descreve o [[análise assintótica|comportamento limitante]] de uma [[função (matemática)|função]] quando o argumento tende a um valor específico ou para o infinito, normalmente, em termos de funções mais simples. É membro de uma família maior de notações conhecida como '''notação Landau''', '''notação Bachmann–Landau''' (nomeada dessa forma por conta de [[Edmund Landau]] e [[Paul Gustav Heinrich Bachmann|Paul Bachmann]]),<ref name="Beigi2011">{{citar livro|autor =Homayoon Beigi|título=Fundamentals of Speaker Recognition|url=http://books.google.com/books?id=qIMDvu3gJCQC&pg=PA777|data=9 de dezembro de 2011|publicado=Springer|isbn=978-0-387-77592-0|páginas=777}}</ref><ref name="Holmes2012">{{citar livro|autor =Mark H. Holmes|título=Introduction to Perturbation Methods|url=http://books.google.com/books?id=EX5iNglbqB4C&pg=PA4|data=5 de dezembro de 2012|publicado=Springer|isbn=978-1-4614-5477-9|páginas=4–}}</ref> ou '''notação assintótica'''. Em [[ciência da computação]], o O-grande é usado para [[Complexidade computacional|classificar algoritmos]] pela forma como eles respondem (''ex.,'' no tempo de processamento ou espaço de trabalho requerido) a mudanças no tamanho da entrada.<ref name=quantumcomplexity>{{citar web|último1 =Mohr|primeiro1 =Austin|título=Quantum Computing in Complexity Theory and Theory of Computation|url=http://www.austinmohr.com/Work_files/complexity.pdf|acessodata=7 de junho de 2014|página=2}}</ref> Na [[teoria analítica dos números]], é usado para estimar o "erro cometido" quando se substitui o tamanho assintótico, ou o tamanho assintótico médio, de uma [[função aritmética]], pelo valor, ou pelo valor médio, que ela recebe num argumento grande e finito. Um exemplo famoso é o problema de estimar o termo restante no [[teorema do número primo]].

A notação O-grande caracteriza funções de acordo com suas taxas de crescimento: funções diferentes com as mesmas taxas de crescimento têm a mesma notação O-grande. A letra O é usada porque a taxa de crescimento de uma função também é referenciada como a ordem de uma função. Uma descrição de uma função em termos de O-grande normalmente provê um [[limite superior e limite inferior|limite superior]] na taxa de crescimento da função. Associada a notação O-grande existem várias outras notações, usando os símbolos ''o'', Ω, ω, e Θ, para descrever outros tipos de relacionamento com taxas de crescimento assintóticas.

A notação O-grande é também usada por muitos campos para prover estimativas similares.

==Definição Formal==
Sejam ''f'' e ''g'' duas funções definidas no mesmo [[subconjunto]] dos [[número real|números reais]] pode-se dizer que

:<math>f(x)=O(g(x))\text{ as }x\to\infty\,</math>

[[se e somente se]] existe uma constante positiva M tal que para todo valor suficientemente grande de ''x'', o valor absoluto de ''f''(''x'') é no máximo M multiplicado pelo valor absoluto de ''g''(''x''). Isto é, ''f''(''x'')&nbsp;=&nbsp;''O''(''g''(''x'')) se e somente se existe um número real positivo ''M'' e um número real ''x''<sub>0</sub> tal que

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

Em muitos contextos, a premissa que estamos interessados, a taxa de crescimento quando a variável ''x'' tende ao infinito, é deixada implícita, e é possível representá-la de forma mais simples em, ''f''(''x'')&nbsp;=&nbsp;''O''(''g''(''x'')).

A notação também pode ser usada para representar o comportamento de ''f'' perto de algum número real ''a'' (muitas vezes, ''a''&nbsp;=&nbsp;0): dizemos

:<math>f(x)=O(g(x))\text{ quando }x\to a\,</math>

se somente se existem números positivos ''δ'' e ''M'' tal que

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

Se ''g''(''x'') são os valores não nulos de ''x'' que são suficientemente próximos a ''a'', ambas essas definições podem ser unidas usando [[limite superior e limite inferior|limite superior]]:

:<math>f(x)=O(g(x))\text{ quando }x \to a\,</math>

se somente se

:<math>\limsup_{x\to a} \left|\frac{f(x)}{g(x)}\right| < \infty.</math><!-- Essas barras de valor absoluto são opcionais. -->

Adicionalmente, a notação ''O''(''g''(''x'')) também é usada para denotar o conjunto de todas as funções ''f''(''x'') que satisfação a relação ''f''(''x'')=''O''(''g''(''x'')). Nesse caso escrevemos

:<math> f(x)\in O(g(x))</math>

==Exemplo==
Numa utilização típica, a definição formal da notação ''O'' não é usada diretamente; ao invés disso, a notação ''O'' de uma função ''f'' é entregue pelas regras de simplificação a seguir:
*Se ''f''(''x'') é a soma de vários termos, o que possuir maior taxa de crescimento é mantido, e todos os outros são omitidos.
*Se ''f''(''x'') é um produto de diversos fatores, quaisquer constantes (termos do produto que não depente de ''x'') são omitidos.
Por exemplo, seja ''f''(''x'') = 6''x''<sup>4</sup>&nbsp;−&nbsp;2''x''<sup>3</sup>&nbsp;+&nbsp;5, e suponha que desejemos simplificar essa função, usando a notação ''O'', para descrever o aumento da sua taxa de crescimento a medida que ''x'' se aproxima do infinito. Essa função é a soma de três termos: 6''x''<sup>4</sup>, −2''x''<sup>3</sup>, e 5. Desses três termos, o que possui maior taxa de crescimento é o que possui maior expoente em função de ''x'', isto é, 6''x''<sup>4</sup>. Agora deve-se aplicar a segunda regra: 6''x''<sup>4</sup> é um produto de 6 e ''x''<sup>4</sup> no qual o primeiro fator não depende de ''x''. Omitir esse fator resulta na forma simplificada ''x''<sup>4</sup>. Assim, dizemos que ''f''(''x'') é um "o-grande" de (''x''<sup>4</sup>). Matematicamente, podemos escrever ''f''(''x'')&nbsp;=&nbsp;''O''(''x''<sup>4</sup>).
Pode-se confirmar esse cálculo usando a definição formal: seja ''f''(''x'')&nbsp;=&nbsp;6''x''<sup>4</sup>&nbsp;−&nbsp;2''x''<sup>3</sup>&nbsp;+&nbsp;5 e ''g''(''x'')&nbsp;=&nbsp;''x''<sup>4</sup>. Aplicando a [[#Definição formal|definição formal]] acima, a afirmação de que ''f''(''x'')&nbsp;=&nbsp;''O''(''x''<sup>4</sup>) é equivalente a sua expansão,
:<math>|f(x)| \le \; M |g(x)|</math>
para alguma escolha adequada de ''x''<sub>0</sub> e ''M'' e para todo ''x''&nbsp;&gt;&nbsp;''x''<sub>0</sub>. Para provar isso, seja ''x''<sub>0</sub>&nbsp;=&nbsp;1 e ''M''&nbsp;=&nbsp;13. Então, para todo ''x''&nbsp;&gt;&nbsp;''x''<sub>0</sub>:
:<math>\begin{align}|6x^4 - 2x^3 + 5| &\le 6x^4 + |2x^3| + 5\\
                                      &\le 6x^4 + 2x^4 + 5x^4\\ 
                                      &= 13x^4\end{align}</math>
então
:<math> |6x^4 - 2x^3 + 5| \le 13 \,x^4 .</math>

==Utilização==
A notação O-grande possui duas grandes áreas de aplicação. Em [[matemática]], é comumente usada para descrever o quão perto uma série finita se aproxima de uma função, especialmente no caso de uma [[Série de Taylor]] truncada ou uma [[expansão assintótica]]. Em [[ciência da computação]], é útil na [[análise de algoritmos]]. Em ambas aplicações, a função ''g''(''x'') que aparece com o ''O''(...) é tipicamente a mais simples possível, omitindo fatores constantes e termos de mais baixa ordem.
Existem dois usos formalmente parecidos, mas visivelmente diferentes, dessa notação: comportamento assintótico no [[infinito]] e comportamento assintótico [[infinitesimal]]. Essa distinção é só na aplicação, mas não no princípio, porém, a definição formal de O-grande é a mesma para ambas as classes, mudando somente os limites para o argumento da função.

===Assintótico no Infinito===
A notação O-grande é útil na [[Complexidade computacional|análise de algoritmos]] por eficiência. Por exemplo, o tempo (ou o número de passos) que ele leva para resolver um problema de tamanho ''n'' pode ser considerado ''T''(''n'') = 4''n''<sup>2</sup> − 2''n'' + 2.
Quando ''n'' cresce, o [[Termo (matemática)|termo]] ''n''<sup>2</sup> vai dominar, de forma que os outros termos podem ser negligenciados—por exemplo quando ''n'' = 500, o termo 4''n''<sup>2</sup> é 1000 vezes maior que o termo 2''n''. Ignorando este termo teria um efeito negligenciável sobre o valor da expressão para muitos propósitos.
Além disso, os [[coeficiente]]s se tornam irrelevantes se comparados a qualquer outra ordem de expressão, de forma que uma expressão contendo um termo n<sup>3</sup> ou n<sup>4</sup>. Mesmo no caso de T (n) = 1.000.000''n''<sup>2</sup>, se ''U''(''n'') = ''n''<sup>3</sup>, este último será sempre superior ao primeiro ''n'' se torna maior do que 1,000,000 (''T''(1,000,000) = 1,000,000<sup>3</sup>= ''U''(1,000,000)). Adicionalmente, o número de passos depende dos detalhes do modelo de máquina no qual o algoritmo roda, mas diferentes tipos de máquina normalmente variam de apenas um fator constante no número de passos necessários para executar o algoritmo.
Então a notação O-grande cobre o restante: podemos escrever tanto
:<math>\ T(n)= O(n^2) \, </math>
quanto
:<math>T(n)\in O(n^2) \, </math>
e dizer que o algoritmo possui complexidade de tempo na ''ordem de n<sup>2</sup>''.
Note que "=" não significa "é igual a" como na senso comum matemático, e sim um "é" mais coloquial, de forma que a segunda expressão é tecnicamente precisa (veja a discussão sobre o "[[#Sinal de igualdade|Sinal de igualdade]]" abaixo) enquanto a primeira é considerada por alguns com um [[abuso de notação]].<ref name="Introduction to Algorithms">Thomas H. Cormen et al., 2001, [http://highered.mcgraw-hill.com/sites/0070131511/ Introduction to Algorithms, Second Edition]</ref>

===Assintótico Infinitesimal===
{{mvar|O}}-grande também pode ser usado para descrever o [[limite de erro|termo de erro]] numa aproximação a uma função matemática. Os termos mais significativos são escritos explicitamente, e então os termos menos significativos são resumidos a um único termo {{mvar|O}}-grande. Considere, por exemplo, [[Função exponencial#Definição formal|série exponencial]] e duas expressões dela que são válidas quando {{mvar|x}} é pequeno:
:<math>\begin{align}
e^x &=1+x+\frac{x^2}{2!}+\frac{x^3}{3!}+\frac{x^4}{4!}+... &\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}</math>
A segunda expressão (a que possui {{math|''O''(''x''<sup>3</sup>)}}) representa que o valor absoluto do erro {{math|''e''<sup>''x''</sup> &minus; (1 + ''x'' + ''x''<sup>2</sup>/2)}} é menor do que alguns tempos constantes {{math|{{!}}''x''<sup>3</sup>{{!}}}} quando {{mvar|x}} é suficientemente próximo de 0.

==Propriedade==
Se a função ''f'' puder ser escrita como uma soma finita de outras funções, então a que cresce mais rápido é que determina a ordem de ''f''(''n''). Por exemplo
:<math>f(n) = 9 \log n + 5 (\log n)^3 + 3n^2 + 2n^3 = O(n^3) \,, \qquad\text{as } n\to\infty  \,\!.</math> <!-- note: "\,\!" forces TeX rendering -->
Em particular, se uma função pode ser delimitada por um [[Função polinomial|polinômio]] em ''n'', então quando ''n'' tende ao infinito, , pode-se desprezar os termos de ''baixa ordem'' do polinômio.
Outra coisa a se considerar é que os conjuntos ''O''(''n''<sup>''c''</sup>) e ''O''(''c''<sup>''n''</sup>) são muito diferentes. Se ''c'' for maior que um, então o último cresce muito mais rápido. Uma função que cresce mais rápido que ''n''<sup>''c''</sup> para qualquer ''c'' é chamada ''superpolinomial''. Uma que cresce mais devagar que qualq''r''ue função exponencial na forma ''c''<sup>''n''</sup> é chamada ''subexponential''. Um algoritmo pode requerer um tempo que seja ao mesmo tempo superpolinomial e subexponential; exemplos disso incluem os algoritmos mais rápidos para [[fatoração de inteiros]] e a função ''n''<sup>log ''n''</sup>.

Nós podemos ignorar quaisquer potências de ''n'' dentro de logaritmos. O conjunto ''O''(log ''n'') é exatamente o mesmo que ''O''(log(''n''<sup>''c''</sup>)). Os logaritmos diferem apenas de um fator constante (já que
log(''n''<sup>''c''</sup>) = ''c'' log ''n'') e assim a notação O-grande ignora isso. Similarmente, logs with bases constantes diferente são equivalentes. Por outro lado, exponenciais com bases diferentes não são de mesma ordem. Por exemplo, 2<sup>''n''</sup> e 3<sup>''n''</sup> não são de mesma ordem.

Mudar unidades pode ou não afetar a ordem dos algoritmos resultantes. Mudar unidades é equivalente a multiplicar a variável apropriada por uma constante onde quer que ela apareça. Por exemplo, se um algoritmo roda na ordem de ''n''<sup>2</sup>, substituir o ''n'' por ''cn'' significa que o algoritmo roda na ordem de ''c''<sup>2</sup>''n''<sup>2</sup>, e a notação O-grande ignora a constante ''c''<sup>2</sup>. Isso pode ser escrito como ''c''<sup>2</sup>''n''<sup>2</sup> = O(''n''<sup>2</sup>). Se, no entanto, um algoritmo roda na ordem de 2<sup>''n''</sup>, substituir ''n'' por ''cn'' nos dá 2<sup>''cn''</sup> = (2<sup>''c''</sup>)<sup>n</sup>. Isso não é equivalente a 2<sup>''n''</sup> em geral.
Mudar variáveis também pode afetar a ordem do algoritmo resultante. Por exemplo, se o tempo de execução de um algoritmo for ''O''(''n'') quando medido em termos do número ''n'' de ''dígitos'' de um número ''x'' na entrada, então o seu tempo de execução é ''O''(log ''x'') quando medido em relação ao próprio número ''x'' da entrada, porque ''n'' = ''O''(log ''x'').

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

===Soma===
:<math> f_1 = O(g_1) \text{ and }
  f_2= O(g_2)\, \Rightarrow f_1 + f_2 = O(|g_1| + |g_2|)\,</math>
::Isso implica que <math> f_1 = O(g) \text{ and } f_2 = O(g) \Rightarrow f_1+f_2 \in O(g) </math>, que significa que <math>O(g)</math> é um [[cone convexo]].
:Se ''f'' e ''g'' são funções positivas, <math>f + O(g) = O(f + g)</math>

===Multiplicação por uma constante===
:Seja ''k'' uma constante. Então:
:<math>\ O(k g) = O(g)</math> se ''k'' é diferente de zero.
:<math>f= O(g) \Rightarrow kf = O(g). </math>

==Múltiplas variáveis==
''O''-grande (e o-pequeno, e Ω...) também pode ser usado com muitas variáveis.
Para definir ''O''-grande formalmente para múltiplas variáveis, suponha que <math>f(\vec{x})</math> e <math>g(\vec{x})</math> são duas funções definidas em um subconjunto de <math>\mathbb{R}^n</math>. Nós dizemos que
:<math>f(\vec{x})\text{ é }O(g(\vec{x}))\text{ quando }\vec{x}\to\infty</math>
se somente se<ref>{{citar livro|último1 =Cormen|primeiro1 =Thomas|último2 =Leiserson|primeiro2 =Charles|último3 =Rivest|primeiro3 =Ronald|último4 =Stein|primeiro4 =Clifford|título=Introduction to Algorithms|data=2009|publicado=MIT|página=53|edição=Third}}</ref>
:<math>\exists M\,\exists C>0\text{ de forma que para todo }\vec{x} \text{ com } x_i \ge M \text{ para algum }i, |f(\vec{x})| \le C |g(\vec{x})|.</math>
Equivalentemente, a condição em que <math>x_i \geq M</math> para algum <math>i</math> pode ser substituída pela condição em que <math>\|\vec{x}\| \ge M</math>, onde <math>\|\vec{x}\|</math> denota a [[Distância de Chebyshev]]. Por exemplo, a sentença
:<math>f(n,m) = n^2 + m^3 + O(n+m) \text{ quando } n,m\to\infty\,</math>
afirma que existem constantes ''C'' e ''M'' tal que
:<math>\forall \|(n, m)\| \geq M:  |g(n,m)| \le C(n+m),</math>
onde ''g''(''n'',''m'') é definido por
:<math>f(n,m) = n^2 + m^3 + g(n,m).\,</math>
Note que essa definição permite a todas as coordenadas de <math>\vec{x}</math> incrementar o infinito. Em particular, a sentença
:<math>f(n,m) = O(n^m) \text{ as } n,m\to\infty\,</math>
(i.e., <math>\exists C\,\exists M\,\forall n\,\forall m\dots</math>) é bem diferente de
:<math>\forall m\colon f(n,m) = O(n^m) \text{ quando } n\to\infty</math>
(i.e., <math>\forall m\,\exists C\,\exists M\,\forall n\dots</math>).

Essa não é a única generalização de O-grande para funções multi-variadas, e na prática, há alguma inconsistência na escolha da definição.<ref>{{citar web|último1 =Howell|primeiro1 =Rodney|título=On Asymptotic Notation with Multiple Variables|url=http://people.cis.ksu.edu/~rhowell/asymptotic.pdf|acessodata=2015-04-23}}</ref>

==Questões de notação==
===Sinal de igualdade===
A afirmação "''f''(''x'') é ''O''(''g''(''x''))" como definido acima é frequentemente escrita como ''f''(''x'')&nbsp;=&nbsp;''O''(''g''(''x'')). Alguns consideram isso como sendo um [[abuso de notação]], desde que o uso de sinais de igualdade poderiam levar a possíveis erros, ao passo que ela sugere uma simetria que a afirmação não carrega. Como [[Nicolaas Govert de Bruijn|de Bruijn]] disse, ''O''(''x'')&nbsp;=&nbsp;''O''(''x''<sup>2</sup>) é verdade, porém ''O''(''x''<sup>2</sup>)&nbsp;=&nbsp;''O''(''x'') não é.<ref>{{citar livro|autor = [[N. G. de Bruijn]] |título=Asymptotic Methods in Analysis |local=Amsterdam |publicado=North-Holland |ano=1958 |páginas=5–7 | url=http://books.google.com/?id=_tnwmvHmVwMC&pg=PA5&vq=%22The+trouble+is%22 | isbn=978-0-486-64221-5}}</ref> [[Donald Knuth|Knuth]] descreve essas afirmações como "igualdades de caminho único", desde que os lados não podem ser revertidos, "nós poderíamos deduzir coisas ridículas como ''n''&nbsp;=&nbsp;''n''<sup>2</sup> das identidades ''n''&nbsp;=&nbsp;''O''(''n''<sup>2</sup>) e ''n''<sup>2</sup>&nbsp;=&nbsp;''O''(''n''<sup>2</sup>)."<ref name="Concrete Mathematics">
{{citar livro|autor =[[Ronald Graham]], Donald Knuth, and Oren Patashnik|título=Concrete Mathematics|local=Reading, Massachusetts|publicado=Addison–Wesley|edição=2|ano=1994 |página=446 |
url=http://books.google.com/?id=pntQAAAAMAAJ&dq=editions:ISBN 0-201-55802-5 | isbn=978-0-201-55802-9}}
</ref>
Por essas razões, seria mais preciso usar a [[notação de conjuntos]] e escrever ''f''(''x'')&nbsp;∈&nbsp;''O''(''g''(''x'')), pensando em ''O''(''g''(''x'')) como a classe de todas as funções ''h''(''x'') tais que |''h''(''x'')|&nbsp;≤&nbsp;''C''|''g''(''x'')| para alguma constante ''C''.<ref name="Concrete Mathematics"/> No entanto, o uso do sinal de igual é habitual. Knuth destacou que "os matemáticos costumam usar o sinal = como eles usam a palavra 'é' em Inglês: Aristóteles é um homem, mas um homem não é necessariamente Aristóteles."<ref>{{citar periódico|autor =Donald Knuth |título=Teach Calculus with Big O |data=junho–julho de 1998 |periódico=[[Notices of the American Mathematical Society]] | volume=45 |número=6 |página=687 | url=http://www.ams.org/notices/199806/commentary.pdf}} ([http://www-cs-staff.stanford.edu/~knuth/ocalc.tex Unabridged version])</ref>

===Outros operadores aritméticos===
A notação O-grande também pode ser usada em conjunto com outros operadores aritméticos em equações mais complicadas. Por exemplo, ''h''(''x'') + ''O''(''f''(''x'')) denota a coleção de funções com crescimento de ''h''(''x'') mais uma parte cujo crescimento é limitado ao de ''f''(''x''). Assim,
:<math>g(x) = h(x) + O(f(x))\,</math>
expressa o mesmo que
:<math>g(x) - h(x) = O(f(x))\,.</math>

====Exemplo {{anchor|Exemplo (Questões de notação)}}====
Suponha que um [[algoritmo]] está sendo desenvolvido para operar num conjunto de ''n'' elementos. Seus desenvolvedores estão interessados em encontrar uma função ''T''(''n'') que expresse quanto tempo o algoritmo vai levar para rodar (numa medida arbitrária de tempo) em termos do número de elementos no conjunto da entrada. O algoritmo funciona primeiro chamando uma sub-rotina que ordena os elementos no conjunto e então executa suas próprias operações. A ordenação tem uma complexidade de tempo conhecida de ''O''(''n''<sup>2</sup>), e depois da sub-rotina, o algoritmo deve executar 55''n''<sup>3</sup>&nbsp;+&nbsp;2''n''&nbsp;+&nbsp;10 passos adicionais antes de terminar. Assim a complexidade de tempo deram do algoritmo pode ser expressa como ''T''(''n'') = 55''n''<sup>3</sup>&nbsp;+&nbsp;''O''(''n''<sup>2</sup>).
Aqui os termos 2''n''+10 estão submissos ao crescimento mais rápido ''O''(''n''<sup>2</sup>). Novamente, essa utilização desconsidera alguns dos significados formais do símbolo "=", mas permite que se use a notação O-grande como uma espécie de marcador de posição conveniente.

===Declaração de variáveis===
Outra característica dessa notação, embora menos excepcional, é que os argumentos da função podem ter de ser inferidas a partir do contexto quando muitas variáveis estiverem envolvidas. Os dois lados direitos das notações O-grande a seguir possuem significados radicalmente diferentes
:<math>f(m) = O(m^n)\,,</math>
:<math>g(n)\,\, = O(m^n)\,.</math>
O primeiro caso indica que ''f''(''m'') apresenta um crescimento polinomial, enquanto que o segundo assumindo ''m'' > 1, afirma que ''g''(''n'') apresenta crescimento exponencial.
Para evitar confusão, alguns autores{{quem}} usam a notação
:<math>g(x) = O(f(x))\,.</math>
em detrimento da menos explícita
:<math>g = O(f)\,,</math>

===Múltiplos usos===
Na forma mais complicada de usar, ''O''(...) pode aparecer em diferentes lugares da equação, inclusive muitas vezes em cada um dos lados. Por exemplo, as seguintes equações são verdade para <math>n\to\infty</math>
:<math>(n+1)^2 = n^2 + O(n)\ </math>
:<math>(n+O(n^{1/2}))(n + O(\log n))^2 = n^3 + O(n^{5/2})\ </math>
:<math>n^{O(1)} = O(e^n).\ </math>
O significado dessas afirmações é: para ''quaisquer'' funções que satisfaçam cada ''O''(...) do lado esquerdo, existem ''algumas'' que satisfaçam ''O''(...) do lado direito, de forma que substituindo todas essas funções na equação os dois lados são iguais. Por exemplo, a terceira equação acima significa que: "Para qualquer função ''f''(''n'') = ''O''(1), existe uma função ''g''(''n'') =''O''(''e''<sup>''n''</sup>) de forma que ''n''<sup>''f''(''n'')</sup> = ''g''(''n'')." Em termos da "notação de conjuntos" acima, o significado é que a classe de funções representada pelo lado esquerdo é um subconjunto da classe de funções representada pelo lado direito. Nesse uso, o "=" é um símbolo formal que, diferentemente do uso comum do "=", não é uma [[relação simétrica]]. Assim, por exemplo, ''n''<sup>''O''(1)</sup> = ''O''(''e''<sup>n</sup>) não implica na afirmação falsa ''O''(''e''<sup>n</sup>) = ''n''<sup>''O''(1)</sup>

==Ordens das funções comuns==
{{Further|Complexidade de tempo#Tabela de complexidade de tempo comum}}

Aqui está uma lista das classes de funções que são comumente encontradas quando analisando a complexidade de tempo de execução de um algoritmo. Em cada caso, ''c'' é uma constante e ''n'' cresce sem limites. As funções de crescimento mais lento estão geralmente listadas primeiro.

{| class="wikitable"
|-
!Notação !! Nome !! Exemplo
|-
|<math>O(1)\,</math> || [[Tempo costante|constante]] || Determinar se um número binário é par ou ímpar; Calcular <math>(-1)^n</math>; Usar uma [[LUT]] de tamanho constante
|-
|<math>O(\log \log n)\,</math> || duplamente logaritmica || Número de comparações gasto para encontrar um item usando busca por interpolação em um array ordenado de valores distribuídos uniformemente
|-
|<math>O(\log n)\,</math> || [[Tempo logarítmico|logarítmico]] || Encontrar um item em uma matriz ordenada com uma busca binária ou uma árvore de busca balanceada, bem como todas as operações num heap binomial
|-
|<math>O((\log n)^c),\;c>1\,</math> || [[Tempo polilogaritmico|polilogarítmico]] || Ordenação de uma cadeia de matrizes pode ser resolvida em tempo polilogarítmico numa [[Máquina de acesso aleatório paralelo]].
|-
|<math>O(n^c),\;0<c<1\,</math> || potencia fracional || Busca em uma [[Árvore k-d]]
|-
|<math>O(n)\,</math> || [[Tempo Linear|linear]] || Encontrar um item em uma lista desordenada ou uma árvore mal-formada (pior caso) ou num array desordenado; adicionar dois inteiros com ''n'' bits por um [[circuito aritmético]]
|-
|<math>O(n\log^* n)\,</math> || n [[logaritmo iterado]] n || Rodar uma [[Triangulação de polígonos|triangulação]] de um simples polígono usando o algoritmo de Seidel, ou a prova do algoritmo de [[União-Busca]]. Perceba que <math>\log^*(n) =
\begin{cases}
 0, & \text{se }n \leq 1 \\
 1 + \log^*(\log n), & \text{se }n>1
\end{cases}</math>
|-
|<math>O(n\log n)=O(\log n!)\,</math> || linearítmico, loglinear, ou quasilinear || Rodar uma [[Transformada Rápida de Fourier]]; [[heapsort]], [[quicksort]] (melhor caso e caso médio), ou [[merge sort]]
|-
|<math>O(n^2)\,</math> || [[Tempo quadrático|quadrático]] || Multiplicar dois números de ''n'' digitos usando um algoritmo simples; [[bubble sort]] (pior caso, ou implementação ingênua), [[Shell sort]], quicksort (pior caso), [[selection sort]] ou [[insertion sort]]
|-
|<math>O(n^c),\;c>1</math> || [[Tempo polinomial|polinomial]] ou algébrico || parsing de [[Gramáticas de árvores disjuntas]]; máximo [[isomofismo]] para [[grafo bipartido|grafos bipartidos]]
|-
|<math>L_n[\alpha,c],\;0 < \alpha < 1=\,</math><br><math>e^{(c+o(1)) (\ln n)^\alpha (\ln \ln n)^{1-\alpha}}</math> || [[notação L]] ou [[Tempo sub-exponencial|sub-exponencial]] || Fatorar um número usando o [[crivo quadrático]] ou [[campo de número de peneira geral]]
|-
|<math>O(c^n),\;c>1</math> || [[Tempo exponencial|exponencial]] || Encontrar a solução exata para o [[Problema do cacheiro viajante]] usando [[programação dinâmica]]; Determinar se duas afirmações lógicas são equivalentes usando [[busca por força bruta]]
|-
|<math>O(n!)\,</math> || [[fatorial]] || Encontrar a solução exata para o [[Problema do caixeiro-viajante|Problema do caixeiro viajante]] usando [[busca por força bruta]]; gerar todas as permutações irrestritas de um [[Conjunto Parcialmente Ordenado|poset]]; encontrar um [[determinante]] com [[Menores|expansão por menores]]; enumerar [[Número de bell|todas as partições de um conjunto]]
|}
A sentença <math>f(n)=O(n!)\,</math> é algumas vezes enfraquecida para <math>f(n)=O\left(n^n\right)</math> para derivar em fórmulas mais simples por complexidade assintótica.
Para qualquer <math>k>0</math> e <math>c>0</math>, <math>O(n^c(\log n)^k)</math> é um conjunto de <math>O(n^{c+\varepsilon })</math> para qualquer <math> \varepsilon >0</math>, então pode ser considerada como um polinomial com uma alta ordem.

==Notações assintóticas relacionadas==
''O''-grande é a notação assintótica mais utilizada para comparação de funções, porém em muitos casos pode ser substituída por Theta-grande Θ para limites mais apertados. Aqui nós definiremos algumas notações relacionadas em termos de ''O''-grande, avançando até a família de notações de Bachmann-Landau, da qual a notação ''O''-grande pertence.
===Notação o-pequeno=== <!-- [[Notação o-pequeno]] redirects here -->
{{redirect|o-pequeno|o jogador de beisebol|Omar Vizquel}}
A sentença informal "''f''(''x'') é o-pequeno de ''g''(''x'')" é escrita formalmente como ''f''(''x'') = ''o''(''g''(''x'')), ou, na notação de conjuntos, ''f''(''x'') ∈ ''o''(''g''(''x'')). Intuitivamente, isso significa que ''g''(''x'') cresce muito mais rápido que ''f''(''x''), ou similarmente, que o crescimento de ''f''(''x'') não é nada comparado ao de ''g''(''x''). Ela assume que ''f'' e ''g'' são duas funções de uma variável. Formalmente, ''f''(''n'')&nbsp;=&nbsp;''o''(''g''(''n'')) (ou ''f''(''n'')&nbsp;∈&nbsp;''o''(''g''(''n''))) quando {{math|''n'' → ∞}} significa que para toda constante positiva ε existe uma constante ''N'' tal que
:<math>|f(n)|\leq\epsilon|g(n)|\qquad\text{para todo }n\geq N~.</math><ref name="Concrete Mathematics"/>

Note que a diferença entre a [[#Definição formal|definição formal]] da notação O-grande, e a definição de o-pequeno: enquanto a primeira deve ser verdade para ''pelo menos uma'' constante ''M'' a segunda deve se verificar para ''todas'' as constantes positivas ε, mesmo as pequenas.<ref name="Introduction to Algorithms"/> Dessa maneira, a notação o-pequeno faz uma afirmação mais forte que a da notação ''O''-grande: toda função que é o-pequeno de ''g'' também é ''O''-grande de ''g'', mas nem toda função que é ''O''-grande de ''g'' também é o-pequeno de ''g'' (por exemplo a própria ''g'' não é, a menos que ela seja identicamente zero perto de ∞).

Se ''g''(''x'') é não nula, ou pelo menos se torna não nula a partir de certo ponto, a relação ''f''(''x'')&nbsp;=&nbsp;''o''(''g''(''x'')) é equivalente a
:<math>\lim_{x \to \infty}\frac{f(x)}{g(x)}=0.</math>
Por exemplo,
* <math>2x  = o(x^2) \,\!</math>
* <math>2x^2 \neq  o(x^2)</math>
* <math>1/x = o(1)</math>
A notação o-pequeno é comum na matemática, porém mais rara em ciência da computação. Em ciência da computação a variável (e o valor da função) é frequentemente um [[número natural]].
Na matemática, a variável e o valor da função não são frequentemente números reais. As propriedades a seguir (expressadas na mais recente notação da [[teoria dos conjuntos]]) pode ser útil:
* <math>c \cdot o(f) = o(f)</math> para todo <math>c \not= 0</math>
* <math>o(f)o(g) \subseteq o(fg)</math>
* <math>o(o(f)) \subseteq o(f)</math>
* <math>o(f) \subset O(f)</math> (e assim a propriedades acima são aplicadas na maioria das combinações de o e O).
Assim como na notação ''O''-grande, a afirmação "<math>f(x)</math> é <math>o(g(x))</math>" é comumente escrita como <math> f(x) = o(g(x))</math>, o que alguns consideram um [[abuso de notação]].

=== Notação Omega-grande ===
Há duas definições muito generalizadas e incompatíveis da afirmação

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

onde ''a'' é um número real, ∞, ou −∞, onde ''f'' e ''g'' são funções reais definidas numa vizinhança de ''a'', e onde ''g'' é positiva nessa vizinhança.

A primeira (cronologicamente) é usada na [[teoria analítica dos números]], e a segunda na [[teoria da complexidade computacional]]. Quando os dois assuntos se encontram, a situação frequentemente leva a confusão.

==== A definição de Hardy–Littlewood ====
Em 1914 [[Godfrey Harold Hardy|G.H. Hardy]] e [[John Edensor Littlewood|J.E. Littlewood]] introduziram o novo símbolo <math>\Omega</math>,<ref name="HL">G. H. Hardy and J. E. Littlewood, "Some problems of Diophantine approximation", Acta Mathematica 37 (1914), p. 225</ref> que é definido da seguinte forma:

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

Assim <math>f(x)=\Omega(g(x))</math> é a negação de <math>f(x)=o(g(x))</math>.

Em 1916 os mesmos autores introduziram os dois novos símbolos <math>\Omega_R</math> e <math>\Omega_L</math>,<ref name="HL2">G. H. Hardy and J. E. Littlewood, « Contribution to the theory of the Riemann zeta-function and the theory of the distribution of primes », ''[[Acta Mathematica]]'', vol. 41, 1916.</ref> definidos assim:

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

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

Como <math>f(x)=\Omega_R(g(x))</math> sendo a negação de <math>f(x)<o(g(x))</math>, e <math>f(x)=\Omega_L(g(x))</math> a negação de <math>f(x)>o(g(x))</math>.

Contrariando a última afirmação de [[Donald Knuth|D.E. Knuth]],<ref name="knuth">Donald Knuth. "[http://www.phil.uu.nl/datastructuren/10-11/knuth_big_omicron.pdf Big Omicron and big Omega and big Theta]", SIGACT News, Apr.-June 1976, 18-24.</ref> [[Edmund Landau]] fez uso desses três símbolos, com o mesmo significado, em 1924.<ref name="landau">E. Landau, "Über die Anzahl der Gitterpunkte in gewissen Bereichen. IV." Nachr. Gesell. Wiss. Gött. Math-phys. Kl. 1924, 137–150.</ref>

Esses símbolos de Hardy-Littlewood são protótipos, que depois de Landau não foram mais usadas exatamente assim.

:<math>\Omega_R</math> se tornou <math>\Omega_+</math>, e <math>\Omega_L</math> se tornou <math>\Omega_-</math>.

Esses três símbolos <math>\Omega, \Omega_+, \Omega_-</math>, assim como <math>f(x)=\Omega_\pm(g(x))</math> (significando que <math>f(x)=\Omega_+(g(x))</math> e <math>f(x)=\Omega_-(g(x))</math> são ambos satisfeitos), são usados atualmente na [[teoria analítica dos números]].<ref>Aleksandar Ivić. The Riemann zeta-function, chapter 9. John Wiley & Sons 1985.</ref>

==== Exemplos simples ====
Temos

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

e de forma mais precisa

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

Temos

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

e de forma mais precisa

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

porém

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

==== A definição de Knuth ====
Em 1976 [[Donald Knuth]] publicou um artigo para justificar o seu uso do símbolo <math>\Omega</math> para descrever uma propriedade mais forte. Knuth escreveu: "Para todas as aplicações que eu já vi em ciência da computação, um requisito mais forte […] é mais apropriado". Ele definiu que

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

com o seguinte comentário: "Apesar de eu ter alterado a definição de Hardy e Littlewood de <math>\Omega</math>, eu sinto que isso está justificado porque a definição deles não está de forma alguma sendo usada em larga escala, e porque existem outras maneiras de dizer o que eles querem dizer nos comparativamente raros casos nos quais a definição deles se aplica".<ref name="knuth"/> Contudo, a definição Hardy–Littlewood havia sido utilizada por pelo menos 25 anos.<ref name="titchmarsh">E. C. Titchmarsh, The Theory of the Riemann Zeta-Function (Oxford; Clarendon Press, 1951)</ref>

===Família de notações de Bachmann–Landau===
{| class="wikitable"
|-
! Notação
! Nome
! Ideia intuitiva
! Definição informal: para um <math>n</math> suficientemente grande...
! Definição formal
<!-- !Alternative definition -->
|-
| <math>f(n) = O(g(n))</math>
| O-grande; Omicron-grande<ref name="knuth"/>
| <math>f</math> é limitada superiormente por <math>g</math> (até no máximo um fator constante) assintoticamente
<!-- |<math>\limsup_{n \to \infty} \left|\frac{f(n)}{g(n)}\right| < \infty</math> -->
|<math>|f(n)|  \leq  k\cdot |g(n)|</math>para algum ''k'' positivo''.''
|<math>\exists k>0 \; \exists n_0 \; \forall n>n_0 \; |f(n)| \leq k\cdot |g(n)|</math>
|-
| <math>f(n) = \Omega(g(n))</math>
| Omega-grande
|''' : '''

Teoria dos números:

<math>f</math> não é dominada por <math>g</math> assintoticamente

Teoria da complexidade:

<math>f</math> é limitada por baixo por <math>g</math> assintoticamente
|Teoria dos números:

<math>f(n)  \geq  k\cdot g(n)</math> por infinitos valores de ''n'' e para algum ''k'' positivo

Teoria da complexidade:

<math>f(n)  \geq  k\cdot g(n)</math> para algum ''k'' positivo
<!--|<math>\liminf_{n \to \infty} \left|\frac{f(n)}{g(n)}\right| > 0 </math> -->
|Teoria dos números:

<math>\exists k>0 \; \forall n_0 \; \exists n>n_0 \; f(n) \geq k\cdot g(n)</math>

Teoria da complexidade:

<math>\exists k>0 \; \exists n_0 \; \forall n>n_0 \; f(n) \geq k\cdot g(n)</math>
|-
|<math>f(n) = \Theta(g(n))</math>
| Theta-grande
| <math>f</math> é limitada por cima e por baixo por <math>g</math> assintoticamente
|<math>k_1\cdot g(n) \leq f(n) \leq k_2\cdot g(n)</math> para algum ''k''<sub>1</sub> e algum ''k''<sub>2</sub> positivos
<!-- |<math>0 < \liminf_{n \to \infty} \left|\frac{f(n)}{g(n)}\right| \leq \limsup_{n \to \infty} \left|\frac{f(n)}{g(n)}\right|< \infty</math> -->
<!--|<math>f(n) \in O(g(n)) \cap \Omega(g(n))</math> -->
|<math>\exists k_1>0 \; \exists k_2>0 \; \exists n_0 \; \forall n>n_0</math>
<math>k_1\cdot g(n) \leq f(n) \leq k_2\cdot g(n)</math>
|-
|<math>f(n) = o(g(n))</math>
| o-pequeno
| <math>f</math> é dominado por <math>g</math> assintoticamente
| <math>|f(n)| \le k\cdot|g(n)|</math>, para todo número positivo <math>k</math>
<!-- |<math>\lim_{n \to \infty} \left|\frac{f(n)}{g(n)}\right| = 0</math> -->
<!-- |<math>\forall \;k>0,\exists \;n(k) : |f(n)| < \; k |g(n)|, \forall n>n(k).</math> -->
|<math>\forall k>0 \; \exists n_0 \; \forall n>n_0 \; |f(n)| \le k\cdot |g(n)|</math>
|-
|<math>f(n) = \omega(g(n))</math>
| Omega-pequeno
| <math>f</math> domina <math>g</math> assintoticamente
| <math>|f(n)| \ge k\cdot|g(n)|</math>, para todo número positivo <math>k</math>
<!-- |<math>\lim_{n \to \infty} \left|\frac{f(n)}{g(n)}\right| = \infty</math> -->
|<math>\forall k>0 \; \exists n_0 \; \forall n>n_0 \  |f(n)| \ge k\cdot |g(n)|</math>
<!-- Sometimes this is expressed as "\forall M<\infty" - alguma preferência? -->
|-
|<math>f(n)\sim g(n)\!</math><!-- force PNG; ~ is often ugly -->
| Na ordem de
| <math>f</math> é igual a <math>g</math> assintoticamente
|<math>f(n)/g(n) \to 1</math>
|<math>\forall \varepsilon>0\;\exists n_0\;\forall n>n_0\;\left|{f(n) \over g(n)}-1\right|<\varepsilon</math>
|}

Além da notação ''O''-grande, as notações Theta-grande e Omega-grande são as duas mais frequentemente utilizadas em ciência da computação; a notação omega-pequeno ω é ocasionalmente usado em ciência da computação.

Além da notação ''O''-grande, as notações o-pequeno, Ω-grande e <math>\sim</math> são as três mais comumente usadas na [[teoria dos números]]; a notação omega-pequeno ω nunca é usada na teoria dos números.

=== Usos em ciência da computação===
{{detalhes|Análise de algoritmos}}
Informalmente, especialmente em ciência da computação, a notação ''O''-grande muitas vezes é permitida a ser um tanto abusada para descrever um limite assintótico apertado, quando usando a notação Theta-grande Θ poderia ser mais factualmente apropriada num dado contexto. {{carece de fontes|reason=Redação (palavras-doninhas) sugerem um postulado principalmente com base em parecer.|data=maio de 2015}} Por exemplo, quando consideramos uma função ''T''(''n'') = 73''n''<sup>3</sup> + 22''n''<sup>2</sup> + 58, todos as afirmações a seguir são geralmente aceitas, mas limites mais apertados (i.e., números 2 e 3 abaixo) são fortemente preferíveis no lugar de limites mais frouxos (i.e., número 1 abaixo).
#''T''(''n'')&nbsp;=&nbsp;''O''(''n''<sup>100</sup>)
#''T''(''n'')&nbsp;=&nbsp;''O''(''n''<sup>3</sup>)
#''T''(''n'')&nbsp;=&nbsp;Θ(''n''<sup>3</sup>)
As afirmações equivalentes em português são respectivamente:
#''T''(''n'') não cresce assintoticamente mais rápido que ''n''<sup>100</sup>
#''T''(''n'') não cresce assintoticamente mais rápido que ''n''<sup>3</sup>
#''T''(''n'') não cresce assintoticamente tão rápido quanto ''n''<sup>3</sup>.
Então apesar dessas três afirmações serem verdade, cada uma delas contem progressivamente mais informação. Em alguns campos, contudo, a notação O-grande (número 2 nas listas acima) seria mais comumente utilizada que a notação Theta-grande (itens número 3 nas listas acima). Por exemplo, se ''T''(''n'') representa o tempo corrente de um algoritmo recém desenvolvido para entrada de tamanho ''n'', os desenvolvedores e usuários do algoritmo podem estar mais inclinados a colocar um limite superior assintótico. Neste caso, afirma-se o tempo que vai levar para rodar, sem fazer uma afirmação explícita sobre o limite inferior assintótico.

===Extensão da notação de Bachmann–Landau===
Outra notação que às vezes é utilizada em ciência da computação é Õ (lê-se ''O-suave''): ''f''(''n'')&nbsp;=&nbsp;''Õ''(''g''(''n'')) é uma abreviação para ''f''(''n'')&nbsp;=&nbsp;''O''(''g''(''n'')&nbsp;log<sup>''k''</sup>&nbsp;''g''(''n'')) para algum ''k''. Essencialmente, ela é a notação O-grande, ignorando fatores logarítmicos porque os efeitos da taxa de crescimento de algumas outras funções super-logarítmicas indicam uma taxa de crescimento explosiva para parâmetros de entrada de grande-porte que é mais importante para prever má performance que os efeitos de alta-granularidade contribuídos pelo(s) fator(es) de crescimento logarítmico. Essa notação é comumente usada para prevenir as "picuinhas" sobre taxas de crescimento que são definidas como limitadas rigorosamente demais para os assuntos discutidos (uma vez que log<sup>''k''</sup>&nbsp;''n'' é sempre ''o''(''n''<sup>ε</sup>) para qualquer constante ''k'' e qualquer ε&nbsp;>&nbsp;0).

Também a [[notação L]], definida como
:<math>L_n[\alpha,c]=O\left(e^{(c+o(1))(\ln n)^\alpha(\ln\ln n)^{1-\alpha}}\right),</math>
é conveniente para funções que estão entre [[Complexidade de tempo#Tempo polinomial|polinomial]] e [[Complexidade de tempo#Tempo exponencial|exponencial]] em termos de <math>\ln n</math>.

==Generalizações e usos relacionados==
A generalização de funções com valores em qualquer [[espaço normado|espaço vetorial normalizado]] é direta (substituindo valores absolutos por normas), onde ''f'' e ''g'' precisam não tomar seus valores no mesmo espaço. Uma generalização a funções ''g'' tomando valores em qualquer [[grupo topológico]] também é possível.

O "processo de limitação" ''x→x<sub>o</sub>'' também pode ser generalizado pela introdução de um [[Filtro (teoria dos conjuntos)|filtro]] arbitrário, i.e. para [[sequência generalizada|sequências generalizadas]] direcionadas ''f'' e ''g''.
A notação ''o'' pode ser usada para definir [[derivada]]s e [[Derivada#Diferenciabilidade|diferenciabilidade]] em espaços bastante gerais, e também equivalência (assintótica) de funções,
:<math> f\sim g \iff (f-g) \in o(g) </math>
que é uma [[relação de equivalência]] e uma noção mais restritiva que o relacionamento "''f'' é Θ(''g'')" acima. (Ele é reduzido a lim ''f'' / ''g'' = 1 se ''f'' e ''g'' são funções valoradas com reais positivos.) Por exemplo, 2''x'' é Θ(''x''), mas 2''x''&nbsp;−&nbsp;''x'' não é ''o''(''x'').

==História (notações de Bachmann–Landau, Hardy, e Vinogradov)==
O símbolo O foi primeiramente introduzido pelo teórico dos números [[Paul Bachmann]] em 1894, no segundo volume do seu livro ''Analytische Zahlentheorie'' ("[[teoria analítica dos números]]"), o primeiro volume deste (que ainda não continha a notação O-grande) foi publicado em 1892.<ref>[[Nicholas J. Higham]], ''Handbook of writing for the mathematical sciences'', SIAM. ISBN 0-89871-420-6, p. 25</ref> O teórico dos números [[Edmund Landau]] a adotou, e foi assim inspirado a introduzir em 1909 a notação o;<ref>Edmund Landau. Handbuch der Lehre von der Verteilung der Primzahlen, Teubner, Leipzig 1909, p.883.</ref> de maneira que ambos são chamados agora de símbolos de Landau. Essas notações foram usadas em matemática aplicada na década de 1950 para análise assintótica.<ref>{{citar livro
|título= Asymptotic Expansions
|último = Erdelyi
|primeiro = A.
|ano= 1956
| isbn = 978-0486603186
}}</ref> O O-grande foi popularizado em ciência da computação por [[Donald Knuth]], que reintroduziu as notações relacionadas Omega e Theta.<ref name="knuth"/> Knuth também notou que a notação Omega foi introduzida por Hardy and Littlewood<ref name="HL" /> sob um significado diferente "≠''o''" (i.e. "não é um ''o'' de"), e propôs a definição acima. A definição original de Hardy e Littlewood (que também foi usada em um artigo de Landau<ref name="landau" />) ainda é usada na teoria dos números (onde a definição de Knuth nunca é usada). De fato, Landau também usou em 1924, no artigo mencionado anteriormente, os símbolos <math>\Omega_R</math> ("direita") e <math>\Omega_L</math> ("esquerda"), que foram introduzidos em 1918 por Hardy e Littlewood,<ref name="HL2" /> e que foram precursores dos símbolos modernos <math>\Omega_+</math> ("não é menor que um o-pequeno de") e <math>\Omega_-</math> ("não é maior que um o-pequeno de"). Assim os símbolos Omega (com seus significados originais) são às vezes referenciados como "símbolos de Landau".

Também, Landau nunca usou os símbolos Theta-grande e omega-pequeno.

Os símbolos de Hardy foram (em termos da notação ''O'' moderna)
:<math> f \preceq g\iff f \in O(g) </math> &nbsp; e &nbsp; <math> f\prec g\iff f\in o(g); </math>

(Hardy, no entanto, nunca definiu ou usou a notação <math>\prec\!\!\prec</math>, nem <math>\ll</math>, como algumas vezes foi reportado).
Também deveria ser percebido que Hardy introduziu os símbolos <math>\preceq </math> e <math>\prec </math> (assim como alguns outros símbolos) em seu folheto de 1910, "Ordens do Infinito", e faz uso deles em três artigos (1910–1913). Em seus quase 400 artigos e livros remanescentes ele consistentemente usa os símbolos de Landau O e o.

A notaçãode Hardy não é mais usada. Por outro lado, na década de 1930,<ref>See for instance "A new estimate for ''G(n)'' in Waring's problem" (Russian). Doklady Akademii Nauk SSSR 5, No 5-6 (1934), 249-253. Translated in English in: Selected works / Ivan Matveevič Vinogradov ; prepared by the Steklov Mathematical Institute of the Academy of Sciences of the USSR on the occasion of his 90th birthday. Springer-Verlag, 1985.</ref> o teórico dos números russo [[Ivan Matveyevich Vinogradov]] introduziu sua notação
<math>\ll</math>, que foi gradualmente mais usada na teoria dos números no lugar da notação <math>O</math>. Temos que

:<math> f\ll g \iff f \in O(g), </math>

e frequentemente ambas as notações são usadas no mesmo artigo.

O O-grande originalmente significava "ordem de" ("Ordnung", Bachmann 1894), e é uma letra latina. Nem Bachmann nem Landau a chamavam de "Omicron". O símbolo foi posteriormente em 1976 visto por Knuth como um [[omicron]] maiúsculo,<ref name="knuth"/> provavelmente em referência a sua definição do símbolo [[Omega]]. O dígito [[0 (número)|zero]] não deve ser usado.

== Ver também ==
* [[Expansão assintótica]]: Aproximação de funções generalizando a fórmula de Taylor
* [[Limite superior e limite inferior]]: Uma explicação de algumas das notações de limite usadas nesse artigo

{{Referências}}

==Leitura complementar==
* [[Paul Bachmann]]. ''Die Analytische Zahlentheorie. Zahlentheorie''. pt. 2 Leipzig: B. G. Teubner, 1894.
* [[Edmund Landau]]. ''Handbuch der Lehre von der Verteilung der Primzahlen''. 2 vols. Leipzig: B. G. Teubner, 1909.
* [[G. H. Hardy]]. ''Orders of Infinity: The 'Infinitärcalcül' of Paul du Bois-Reymond'', 1910.
* [[Donald Knuth]]. ''The Art of Computer Programming'', Volume 1: ''Fundamental Algorithms'', Third Edition. Addison–Wesley, 1997. ISBN 0-201-89683-4. Section 1.2.11: Asymptotic Representations, pp.&nbsp;107–123.
* [[Paul Vitanyi]], [[Lambert Meertens]], Big Omega versus the wild functions, Bull. European Association Theoret. Comput. Sci. (EATCS) 22(1984), 14-19. Also: ACM-SIGACT News, 16:4(1984) 56-59.
* [[Thomas H. Cormen]], [[Charles E. Leiserson]], [[Ronald L. Rivest]], and [[Clifford Stein]]. ''[[Introduction to Algorithms]]'', Second Edition. MIT Press and McGraw–Hill, 2001. ISBN 0-262-03293-7. Section 3.1: Asymptotic notation, pp.&nbsp;41–50.
* {{citar livro|autor = [[Michael Sipser]] |ano= 1997 |título= Introduction to the Theory of Computation |publicado= PWS Publishing | isbn = 0-534-94728-X}} Pages 226–228 of section 7.1: Measuring complexity.
* Jeremy Avigad, Kevin Donnelly. ''[http://www.andrew.cmu.edu/~avigad/Papers/bigo.pdf Formalizing O notation in Isabelle/HOL]''
* Paul E. Black, [http://www.nist.gov/dads/HTML/bigOnotation.html "big-O notation"], in ''Dictionary of Algorithms and Data Structures'' [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 11 March 2005. Retrieved December 16, 2006.
* Paul E. Black, [http://www.nist.gov/dads/HTML/littleOnotation.html "little-o notation"], in ''Dictionary of Algorithms and Data Structures'' [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 17 December 2004. Retrieved December 16, 2006.
* Paul E. Black, [http://www.nist.gov/dads/HTML/omegaCapital.html "Ω"], in ''Dictionary of Algorithms and Data Structures'' [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 17 December 2004. Retrieved December 16, 2006.
* Paul E. Black, [http://www.nist.gov/dads/HTML/omega.html "ω"], in ''Dictionary of Algorithms and Data Structures'' [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 29 November 2004. Retrieved December 16, 2006.
* Paul E. Black, [http://www.nist.gov/dads/HTML/theta.html "Θ"], in ''Dictionary of Algorithms and Data Structures'' [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 17 December 2004. Retrieved December 16, 2006.

== Ligações externas ==
{{wikibooks|Data Structures|Asymptotic Notation#Big-O Notation|Big-O Notation}}
* [http://oeis.org/wiki/Growth_of_sequences Growth of sequences—OEIS (Online Encyclopedia of Integer Sequences) Wiki]
* [https://web.archive.org/web/20110604215018/http://www.soe.ucsc.edu/classes/cmps102/Spring04/TantaloAsymp.pdf Introduction to Asymptotic Notations]
* [http://mathworld.wolfram.com/LandauSymbols.html Landau Symbols]
* [http://www.perlmonks.org/?node_id=573138 Big-O Notation – What is it good for]

{{DEFAULTSORT:Notação O-grande}}
[[Categoria:Notação matemática]]
[[Categoria:Complexidade]]