Grande-O

Na matemática, a notação O-grande descreve o comportamento limitante de uma 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 Bachmann),^[1][2] ou notação assintótica. Em ciência da computação, o O-grande é usado para 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.^[3] 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 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.

Sejam f e g duas funções definidas no mesmo subconjunto dos números reais pode-se dizer que

${\displaystyle f(x)=O(g(x)){\text{ as }}x\to \infty \,}$

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) = O(g(x)) se e somente se existe um número real positivo M e um número real x₀ tal que

${\displaystyle |f(x)|\leq \;M|g(x)|{\text{ para todo }}x\geq x_{0}.}$

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) = 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 = 0): dizemos

${\displaystyle f(x)=O(g(x)){\text{ quando }}x\to a\,}$

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

${\displaystyle |f(x)|\leq \;M|g(x)|{\text{ for }}|x-a|<\delta .}$

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:

${\displaystyle f(x)=O(g(x)){\text{ quando }}x\to a\,}$

se somente se

${\displaystyle \limsup _{x\to a}\left|{\frac {f(x)}{g(x)}}\right|<\infty .}$

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

${\displaystyle f(x)\in O(g(x))}$

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) = 6x⁴ − 2x³ + 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: 6x⁴, −2x³, e 5. Desses três termos, o que possui maior taxa de crescimento é o que possui maior expoente em função de x, isto é, 6x⁴. Agora deve-se aplicar a segunda regra: 6x⁴ é um produto de 6 e x⁴ no qual o primeiro fator não depende de x. Omitir esse fator resulta na forma simplificada x⁴. Assim, dizemos que f(x) é um "o-grande" de (x⁴). Matematicamente, podemos escrever f(x) = O(x⁴). Pode-se confirmar esse cálculo usando a definição formal: seja f(x) = 6x⁴ − 2x³ + 5 e g(x) = x⁴. Aplicando a definição formal acima, a afirmação de que f(x) = O(x⁴) é equivalente a sua expansão,

${\displaystyle |f(x)|\leq \;M|g(x)|}$

para alguma escolha adequada de x₀ e M e para todo x > x₀. Para provar isso, seja x₀ = 1 e M = 13. Então, para todo x > x₀:

${\displaystyle {\begin{aligned}|6x^{4}-2x^{3}+5|&\leq 6x^{4}+|2x^{3}|+5\\&\leq 6x^{4}+2x^{4}+5x^{4}\\&=13x^{4}\end{aligned}}}$

então

${\displaystyle |6x^{4}-2x^{3}+5|\leq 13\,x^{4}.}$

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.

A notação O-grande é útil na 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) = 4n² − 2n + 2. Quando n cresce, o termo n² vai dominar, de forma que os outros termos podem ser negligenciados—por exemplo quando n = 500, o termo 4n² é 1000 vezes maior que o termo 2n. Ignorando este termo teria um efeito negligenciável sobre o valor da expressão para muitos propósitos. Além disso, os coeficientes se tornam irrelevantes se comparados a qualquer outra ordem de expressão, de forma que uma expressão contendo um termo n³ ou n⁴. Mesmo no caso de T (n) = 1.000.000n², se U(n) = n³, este último será sempre superior ao primeiro n se torna maior do que 1,000,000 (T(1,000,000) = 1,000,000³= 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

${\displaystyle \ T(n)=O(n^{2})\,}$

quanto

${\displaystyle T(n)\in O(n^{2})\,}$

e dizer que o algoritmo possui complexidade de tempo na ordem de n². 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" abaixo) enquanto a primeira é considerada por alguns com um abuso de notação.^[4]

O-grande também pode ser usado para descrever o 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 O-grande. Considere, por exemplo, série exponencial e duas expressões dela que são válidas quando x é pequeno:

${\displaystyle {\begin{aligned}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{aligned}}}$

A segunda expressão (a que possui O(x³)) representa que o valor absoluto do erro e^x − (1 + x + x²/2) é menor do que alguns tempos constantes |x³| quando x é suficientemente próximo de 0.

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

${\displaystyle f(n)=9\log n+5(\log n)^{3}+3n^{2}+2n^{3}=O(n^{3})\,,\qquad {\text{as }}n\to \infty \,\!.}$

Em particular, se uma função pode ser delimitada por um 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^c) e O(cⁿ) 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^c para qualquer c é chamada superpolinomial. Uma que cresce mais devagar que qualqrue função exponencial na forma cⁿ é 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^{log n}.

Nós podemos ignorar quaisquer potências de n dentro de logaritmos. O conjunto O(log n) é exatamente o mesmo que O(log(n^c)). Os logaritmos diferem apenas de um fator constante (já que log(n^c) = 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ⁿ e 3ⁿ 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², substituir o n por cn significa que o algoritmo roda na ordem de c²n², e a notação O-grande ignora a constante c². Isso pode ser escrito como c²n² = O(n²). Se, no entanto, um algoritmo roda na ordem de 2ⁿ, substituir n por cn nos dá 2^cn = (2^c)ⁿ. Isso não é equivalente a 2ⁿ 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).

${\displaystyle f_{1}=O(g_{1}){\text{ e }}f_{2}=O(g_{2})\,\Rightarrow f_{1}f_{2}=O(g_{1}g_{2})\,}$

${\displaystyle f\cdot O(g)=O(fg)}$

${\displaystyle f_{1}=O(g_{1}){\text{ and }}f_{2}=O(g_{2})\,\Rightarrow f_{1}+f_{2}=O(|g_{1}|+|g_{2}|)\,}$

Isso implica que ${\displaystyle f_{1}=O(g){\text{ and }}f_{2}=O(g)\Rightarrow f_{1}+f_{2}\in O(g)}$, que significa que ${\displaystyle O(g)}$ é um cone convexo.

Se f e g são funções positivas, ${\displaystyle f+O(g)=O(f+g)}$

Seja k uma constante. Então:

${\displaystyle \ O(kg)=O(g)}$ se k é diferente de zero.

${\displaystyle f=O(g)\Rightarrow kf=O(g).}$

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 ${\displaystyle f({\vec {x}})}$ e ${\displaystyle g({\vec {x}})}$ são duas funções definidas em um subconjunto de ${\displaystyle \mathbb {R} ^{n}}$. Nós dizemos que

${\displaystyle f({\vec {x}}){\text{ é }}O(g({\vec {x}})){\text{ quando }}{\vec {x}}\to \infty }$

se somente se^[5]

${\displaystyle \exists M\,\exists C>0{\text{ de forma que para todo }}{\vec {x}}{\text{ com }}x_{i}\geq M{\text{ para algum }}i,|f({\vec {x}})|\leq C|g({\vec {x}})|.}$

Equivalentemente, a condição em que ${\displaystyle x_{i}\geq M}$ para algum ${\displaystyle i}$ pode ser substituída pela condição em que ${\displaystyle \|{\vec {x}}\|\geq M}$, onde ${\displaystyle \|{\vec {x}}\|}$ denota a Distância de Chebyshev. Por exemplo, a sentença

${\displaystyle f(n,m)=n^{2}+m^{3}+O(n+m){\text{ quando }}n,m\to \infty \,}$

afirma que existem constantes C e M tal que

${\displaystyle \forall \|(n,m)\|\geq M:|g(n,m)|\leq C(n+m),}$

onde g(n,m) é definido por

${\displaystyle f(n,m)=n^{2}+m^{3}+g(n,m).\,}$

Note que essa definição permite a todas as coordenadas de ${\displaystyle {\vec {x}}}$ incrementar o infinito. Em particular, a sentença

${\displaystyle f(n,m)=O(n^{m}){\text{ as }}n,m\to \infty \,}$

(i.e., ${\displaystyle \exists C\,\exists M\,\forall n\,\forall m\dots }$) é bem diferente de

${\displaystyle \forall m\colon f(n,m)=O(n^{m}){\text{ quando }}n\to \infty }$

(i.e., ${\displaystyle \forall m\,\exists C\,\exists M\,\forall n\dots }$).

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.^[6]

A afirmação "f(x) é O(g(x))" como definido acima é frequentemente escrita como f(x) = 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 de Bruijn disse, O(x) = O(x²) é verdade, porém O(x²) = O(x) não é.^[7] 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 = n² das identidades n = O(n²) e n² = O(n²)."^[8] Por essas razões, seria mais preciso usar a notação de conjuntos e escrever f(x) ∈ O(g(x)), pensando em O(g(x)) como a classe de todas as funções h(x) tais que |h(x)| ≤ C|g(x)| para alguma constante C.^[8] 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."^[9]

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,

${\displaystyle g(x)=h(x)+O(f(x))\,}$

expressa o mesmo que

${\displaystyle g(x)-h(x)=O(f(x))\,.}$

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²), e depois da sub-rotina, o algoritmo deve executar 55n³ + 2n + 10 passos adicionais antes de terminar. Assim a complexidade de tempo deram do algoritmo pode ser expressa como T(n) = 55n³ + O(n²). Aqui os termos 2n+10 estão submissos ao crescimento mais rápido O(n²). 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.

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

${\displaystyle f(m)=O(m^{n})\,,}$

${\displaystyle g(n)\,\,=O(m^{n})\,.}$

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

${\displaystyle g(x)=O(f(x))\,.}$

em detrimento da menos explícita

${\displaystyle g=O(f)\,,}$

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 ${\displaystyle n\to \infty }$

${\displaystyle (n+1)^{2}=n^{2}+O(n)\ }$

${\displaystyle (n+O(n^{1/2}))(n+O(\log n))^{2}=n^{3}+O(n^{5/2})\ }$

${\displaystyle n^{O(1)}=O(e^{n}).\ }$

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ⁿ) de forma que n^f(n) = 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^O(1) = O(eⁿ) não implica na afirmação falsa O(eⁿ) = n^O(1)

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.

Notação	Nome	Exemplo
${\displaystyle O(1)\,}$	constante	Determinar se um número binário é par ou ímpar; Calcular ${\displaystyle (-1)^{n}}$; Usar uma LUT de tamanho constante
${\displaystyle O(\log \log n)\,}$	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
${\displaystyle O(\log n)\,}$	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
${\displaystyle O((\log n)^{c}),\;c>1\,}$	polilogarítmico	Ordenação de uma cadeia de matrizes pode ser resolvida em tempo polilogarítmico numa Máquina de acesso aleatório paralelo.
${\displaystyle O(n^{c}),\;0<c<1\,}$	potencia fracional	Busca em uma Árvore k-d
${\displaystyle O(n)\,}$	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
${\displaystyle O(n\log ^{*}n)\,}$	n logaritmo iterado n	Rodar uma triangulação de um simples polígono usando o algoritmo de Seidel, ou a prova do algoritmo de União-Busca. Perceba que ${\displaystyle \log ^{*}(n)={\begin{cases}0,&{\text{se }}n\leq 1\\1+\log ^{*}(\log n),&{\text{se }}n>1\end{cases}}}$
${\displaystyle O(n\log n)=O(\log n!)\,}$	linearítmico, loglinear, ou quasilinear	Rodar uma Transformada Rápida de Fourier; heapsort, quicksort (melhor caso e caso médio), ou merge sort
${\displaystyle O(n^{2})\,}$	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
${\displaystyle O(n^{c}),\;c>1}$	polinomial ou algébrico	parsing de Gramáticas de árvores disjuntas; máximo isomofismo para grafos bipartidos
${\displaystyle L_{n}[\alpha ,c],\;0<\alpha <1=\,}$ ${\displaystyle e^{(c+o(1))(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }}}$	notação L ou sub-exponencial	Fatorar um número usando o crivo quadrático ou campo de número de peneira geral
${\displaystyle O(c^{n}),\;c>1}$	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
${\displaystyle O(n!)\,}$	fatorial	Encontrar a solução exata para o Problema do caixeiro viajante usando busca por força bruta; gerar todas as permutações irrestritas de um poset; encontrar um determinante com expansão por menores; enumerar todas as partições de um conjunto

A sentença ${\displaystyle f(n)=O(n!)\,}$ é algumas vezes enfraquecida para ${\displaystyle f(n)=O\left(n^{n}\right)}$ para derivar em fórmulas mais simples por complexidade assintótica. Para qualquer ${\displaystyle k>0}$ e ${\displaystyle c>0}$, ${\displaystyle O(n^{c}(\log n)^{k})}$ é um conjunto de ${\displaystyle O(n^{c+\varepsilon })}$ para qualquer ${\displaystyle \varepsilon >0}$, então pode ser considerada como um polinomial com uma alta ordem.

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.

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) = o(g(n)) (ou f(n) ∈ o(g(n))) quando n → ∞ significa que para toda constante positiva ε existe uma constante N tal que

${\displaystyle |f(n)|\leq \epsilon |g(n)|\qquad {\text{para todo }}n\geq N~.}$^[8]

Note que a diferença entre a 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.^[4] 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) = o(g(x)) é equivalente a

${\displaystyle \lim _{x\to \infty }{\frac {f(x)}{g(x)}}=0.}$

Por exemplo,

• ${\displaystyle 2x=o(x^{2})\,\!}$
• ${\displaystyle 2x^{2}\neq o(x^{2})}$
• ${\displaystyle 1/x=o(1)}$

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:

• ${\displaystyle c\cdot o(f)=o(f)}$ para todo ${\displaystyle c\not =0}$
• ${\displaystyle o(f)o(g)\subseteq o(fg)}$
• ${\displaystyle o(o(f))\subseteq o(f)}$
• ${\displaystyle o(f)\subset O(f)}$ (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 "${\displaystyle f(x)}$ é ${\displaystyle o(g(x))}$" é comumente escrita como ${\displaystyle f(x)=o(g(x))}$, o que alguns consideram um abuso de notação.

Há duas definições muito generalizadas e incompatíveis da afirmação

${\displaystyle f(x)=\Omega (g(x))\ (x\rightarrow a),}$

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.

Em 1914 G.H. Hardy e J.E. Littlewood introduziram o novo símbolo ${\displaystyle \Omega }$,^[10] que é definido da seguinte forma:

${\displaystyle f(x)=\Omega (g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\limsup _{x\to \infty }\left|{\frac {f(x)}{g(x)}}\right|>0}$.

Assim ${\displaystyle f(x)=\Omega (g(x))}$ é a negação de ${\displaystyle f(x)=o(g(x))}$.

Em 1916 os mesmos autores introduziram os dois novos símbolos ${\displaystyle \Omega _{R}}$ e ${\displaystyle \Omega _{L}}$,^[11] definidos assim:

${\displaystyle f(x)=\Omega _{R}(g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\limsup _{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}$.

Como ${\displaystyle f(x)=\Omega _{R}(g(x))}$ sendo a negação de ${\displaystyle f(x)<o(g(x))}$, e ${\displaystyle f(x)=\Omega _{L}(g(x))}$ a negação de ${\displaystyle f(x)>o(g(x))}$.

Contrariando a última afirmação de D.E. Knuth,^[12] Edmund Landau fez uso desses três símbolos, com o mesmo significado, em 1924.^[13]

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

${\displaystyle \Omega _{R}}$ se tornou ${\displaystyle \Omega _{+}}$, e ${\displaystyle \Omega _{L}}$ se tornou ${\displaystyle \Omega _{-}}$.

Esses três símbolos ${\displaystyle \Omega ,\Omega _{+},\Omega _{-}}$, assim como ${\displaystyle f(x)=\Omega _{\pm }(g(x))}$ (significando que ${\displaystyle f(x)=\Omega _{+}(g(x))}$ e ${\displaystyle f(x)=\Omega _{-}(g(x))}$ são ambos satisfeitos), são usados atualmente na teoria analítica dos números.^[14]

Temos

${\displaystyle \sin x=\Omega (1)\ (x\rightarrow \infty ),}$

e de forma mais precisa

${\displaystyle \sin x=\Omega _{\pm }(1)\ (x\rightarrow \infty ).}$

Temos

${\displaystyle \sin x+1=\Omega (1)\ (x\rightarrow \infty ),}$

e de forma mais precisa

${\displaystyle \sin x+1=\Omega _{+}(1)\ (x\rightarrow \infty );}$

porém

${\displaystyle \sin x+1\not =\Omega _{-}(1)\ (x\rightarrow \infty ).}$

Em 1976 Donald Knuth publicou um artigo para justificar o seu uso do símbolo ${\displaystyle \Omega }$ 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

${\displaystyle f(x)=\Omega (g(x))\Leftrightarrow g(x)=O(f(x))}$

com o seguinte comentário: "Apesar de eu ter alterado a definição de Hardy e Littlewood de ${\displaystyle \Omega }$, 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".^[12] Contudo, a definição Hardy–Littlewood havia sido utilizada por pelo menos 25 anos.^[15]

Notação	Nome	Ideia intuitiva	Definição informal: para um ${\displaystyle n}$ suficientemente grande...	Definição formal
${\displaystyle f(n)=O(g(n))}$	O-grande; Omicron-grande[12]	${\displaystyle f}$ é limitada superiormente por ${\displaystyle g}$ (até no máximo um fator constante) assintoticamente	${\displaystyle |f(n)|\leq k\cdot |g(n)|}$para algum k positivo.	${\displaystyle \exists k>0\;\exists n_{0}\;\forall n>n_{0}\;|f(n)|\leq k\cdot |g(n)|}$
${\displaystyle f(n)=\Omega (g(n))}$	Omega-grande	: Teoria dos números: ${\displaystyle f}$ não é dominada por ${\displaystyle g}$ assintoticamente Teoria da complexidade: ${\displaystyle f}$ é limitada por baixo por ${\displaystyle g}$ assintoticamente	Teoria dos números: ${\displaystyle f(n)\geq k\cdot g(n)}$ por infinitos valores de n e para algum k positivo Teoria da complexidade: ${\displaystyle f(n)\geq k\cdot g(n)}$ para algum k positivo	Teoria dos números: ${\displaystyle \exists k>0\;\forall n_{0}\;\exists n>n_{0}\;f(n)\geq k\cdot g(n)}$ Teoria da complexidade: ${\displaystyle \exists k>0\;\exists n_{0}\;\forall n>n_{0}\;f(n)\geq k\cdot g(n)}$
${\displaystyle f(n)=\Theta (g(n))}$	Theta-grande	${\displaystyle f}$ é limitada por cima e por baixo por ${\displaystyle g}$ assintoticamente	${\displaystyle k_{1}\cdot g(n)\leq f(n)\leq k_{2}\cdot g(n)}$ para algum k1 e algum k2 positivos	${\displaystyle \exists k_{1}>0\;\exists k_{2}>0\;\exists n_{0}\;\forall n>n_{0}}$ ${\displaystyle k_{1}\cdot g(n)\leq f(n)\leq k_{2}\cdot g(n)}$
${\displaystyle f(n)=o(g(n))}$	o-pequeno	${\displaystyle f}$ é dominado por ${\displaystyle g}$ assintoticamente	${\displaystyle |f(n)|\leq k\cdot |g(n)|}$, para todo número positivo ${\displaystyle k}$	${\displaystyle \forall k>0\;\exists n_{0}\;\forall n>n_{0}\;|f(n)|\leq k\cdot |g(n)|}$
${\displaystyle f(n)=\omega (g(n))}$	Omega-pequeno	${\displaystyle f}$ domina ${\displaystyle g}$ assintoticamente	${\displaystyle |f(n)|\geq k\cdot |g(n)|}$, para todo número positivo ${\displaystyle k}$	${\displaystyle \forall k>0\;\exists n_{0}\;\forall n>n_{0}\ |f(n)|\geq k\cdot |g(n)|}$
${\displaystyle f(n)\sim g(n)\!}$	Na ordem de	${\displaystyle f}$ é igual a ${\displaystyle g}$ assintoticamente	${\displaystyle f(n)/g(n)\to 1}$	${\displaystyle \forall \varepsilon >0\;\exists n_{0}\;\forall n>n_{0}\;\left|{f(n) \over g(n)}-1\right|<\varepsilon }$

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 ${\displaystyle \sim }$ 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.

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?]} Por exemplo, quando consideramos uma função T(n) = 73n³ + 22n² + 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).

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

As afirmações equivalentes em português são respectivamente:

1. T(n) não cresce assintoticamente mais rápido que n¹⁰⁰
2. T(n) não cresce assintoticamente mais rápido que n³
3. T(n) não cresce assintoticamente tão rápido quanto n³.

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.

Outra notação que às vezes é utilizada em ciência da computação é Õ (lê-se O-suave): f(n) = Õ(g(n)) é uma abreviação para f(n) = O(g(n) log^k 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^k n é sempre o(n^ε) para qualquer constante k e qualquer ε > 0).

Também a notação L, definida como

${\displaystyle L_{n}[\alpha ,c]=O\left(e^{(c+o(1))(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }}\right),}$

é conveniente para funções que estão entre polinomial e exponencial em termos de ${\displaystyle \ln n}$.

A generalização de funções com valores em qualquer 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_o também pode ser generalizado pela introdução de um filtro arbitrário, i.e. para sequências generalizadas direcionadas f e g. A notação o pode ser usada para definir derivadas e diferenciabilidade em espaços bastante gerais, e também equivalência (assintótica) de funções,

${\displaystyle f\sim g\iff (f-g)\in o(g)}$

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, 2x é Θ(x), mas 2x − x não é o(x).

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.^[16] O teórico dos números Edmund Landau a adotou, e foi assim inspirado a introduzir em 1909 a notação o;^[17] 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.^[18] O O-grande foi popularizado em ciência da computação por Donald Knuth, que reintroduziu as notações relacionadas Omega e Theta.^[12] Knuth também notou que a notação Omega foi introduzida por Hardy and Littlewood^[10] 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^[13]) 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 ${\displaystyle \Omega _{R}}$ ("direita") e ${\displaystyle \Omega _{L}}$ ("esquerda"), que foram introduzidos em 1918 por Hardy e Littlewood,^[11] e que foram precursores dos símbolos modernos ${\displaystyle \Omega _{+}}$ ("não é menor que um o-pequeno de") e ${\displaystyle \Omega _{-}}$ ("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)

${\displaystyle f\preceq g\iff f\in O(g)}$   e   ${\displaystyle f\prec g\iff f\in o(g);}$

(Hardy, no entanto, nunca definiu ou usou a notação ${\displaystyle \prec \!\!\prec }$, nem ${\displaystyle \ll }$, como algumas vezes foi reportado). Também deveria ser percebido que Hardy introduziu os símbolos ${\displaystyle \preceq }$ e ${\displaystyle \prec }$ (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,^[19] o teórico dos números russo Ivan Matveyevich Vinogradov introduziu sua notação ${\displaystyle \ll }$, que foi gradualmente mais usada na teoria dos números no lugar da notação ${\displaystyle O}$. Temos que

${\displaystyle f\ll g\iff f\in O(g),}$

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,^[12] provavelmente em referência a sua definição do símbolo Omega. O dígito zero não deve ser usado.

• 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

1. ↑ Homayoon Beigi (9 de dezembro de 2011). Fundamentals of Speaker Recognition. [S.l.]: Springer. 777 páginas. ISBN 978-0-387-77592-0 
2. ↑ Mark H. Holmes (5 de dezembro de 2012). Introduction to Perturbation Methods. [S.l.]: Springer. pp. 4–. ISBN 978-1-4614-5477-9 
3. ↑ Mohr, Austin. «Quantum Computing in Complexity Theory and Theory of Computation» (PDF). p. 2. Consultado em 7 de junho de 2014 
4. ↑ ^{a b} Thomas H. Cormen et al., 2001, Introduction to Algorithms, Second Edition
5. ↑ Cormen, Thomas; Leiserson, Charles; Rivest, Ronald; Stein, Clifford (2009). Introduction to Algorithms Third ed. [S.l.]: MIT. p. 53 
6. ↑ Howell, Rodney. «On Asymptotic Notation with Multiple Variables» (PDF). Consultado em 23 de abril de 2015 
7. ↑ N. G. de Bruijn (1958). Asymptotic Methods in Analysis. Amsterdam: North-Holland. pp. 5–7. ISBN 978-0-486-64221-5 
8. ↑ ^{a b c} Ronald Graham, Donald Knuth, and Oren Patashnik (1994). 0-201-55802-5 Concrete Mathematics Verifique valor |url= (ajuda) 2 ed. Reading, Massachusetts: Addison–Wesley. p. 446. ISBN 978-0-201-55802-9  !CS1 manut: Nomes múltiplos: lista de autores (link)
9. ↑ Donald Knuth (junho–julho de 1998). «Teach Calculus with Big O» (PDF). Notices of the American Mathematical Society. 45 (6): 687  (Unabridged version)
10. ↑ ^{a b} G. H. Hardy and J. E. Littlewood, "Some problems of Diophantine approximation", Acta Mathematica 37 (1914), p. 225
11. ↑ ^{a b} 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.
12. ↑ ^{a b c d e} Donald Knuth. "Big Omicron and big Omega and big Theta", SIGACT News, Apr.-June 1976, 18-24.
13. ↑ ^{a b} E. Landau, "Über die Anzahl der Gitterpunkte in gewissen Bereichen. IV." Nachr. Gesell. Wiss. Gött. Math-phys. Kl. 1924, 137–150.
14. ↑ Aleksandar Ivić. The Riemann zeta-function, chapter 9. John Wiley & Sons 1985.
15. ↑ E. C. Titchmarsh, The Theory of the Riemann Zeta-Function (Oxford; Clarendon Press, 1951)
16. ↑ Nicholas J. Higham, Handbook of writing for the mathematical sciences, SIAM. ISBN 0-89871-420-6, p. 25
17. ↑ Edmund Landau. Handbuch der Lehre von der Verteilung der Primzahlen, Teubner, Leipzig 1909, p.883.
18. ↑ Erdelyi, A. (1956). Asymptotic Expansions. [S.l.: s.n.] ISBN 978-0486603186 
19. ↑ 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.

Leitura complementar

[editar | editar código-fonte]

• 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. 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. 41–50.
• Michael Sipser (1997). Introduction to the Theory of Computation. [S.l.]: PWS Publishing. ISBN 0-534-94728-X  Pages 226–228 of section 7.1: Measuring complexity.
• Jeremy Avigad, Kevin Donnelly. Formalizing O notation in Isabelle/HOL
• Paul E. Black, "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, "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, "Ω", 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, "ω", 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, "Θ", 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

[editar | editar código-fonte]

O wikilivro Data Structures tem uma página sobre Big-O Notation

• Growth of sequences—OEIS (Online Encyclopedia of Integer Sequences) Wiki
• Introduction to Asymptotic Notations
• Landau Symbols
• Big-O Notation – What is it good for