400px|thumb|Exemplo da notação O-grande: ∈ O() de forma que existem c > 0 (e.g., c = 1) e x0 (e.g., x0 = 5) tal que ≤ c sempre que x ≥ x0. 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), 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. 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.
Definição Formal Sejam f e g duas funções definidas no mesmo subconjunto dos números reais pode-se dizer que
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 x0 tal que
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
se somente se existem números positivos δ e M tal que
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:
se somente se
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
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) = 6x4 − 2x3 + 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: 6x4, −2x3, e 5. Desses três termos, o que possui maior taxa de crescimento é o que possui maior expoente em função de x, isto é, 6x4. Agora deve-se aplicar a segunda regra: 6x4 é um produto de 6 e x4 no qual o primeiro fator não depende de x. Omitir esse fator resulta na forma simplificada x4. Assim, dizemos que f(x) é um "o-grande" de (x4). Matematicamente, podemos escrever f(x) = O(x4). Pode-se confirmar esse cálculo usando a definição formal: seja f(x) = 6x4 − 2x3 + 5 e g(x) = x4. Aplicando a definição formal acima, a afirmação de que f(x) = O(x4) é equivalente a sua expansão,
para alguma escolha adequada de x0 e M e para todo x > x0. Para provar isso, seja x0 = 1 e M = 13. Então, para todo x > x0:
então
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 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) = 4n2 − 2n + 2. Quando n cresce, o termo n2 vai dominar, de forma que os outros termos podem ser negligenciados—por exemplo quando n = 500, o termo 4n2 é 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 n3 ou n4. Mesmo no caso de T (n) = 1.000.000n2, se U(n) = n3, este último será sempre superior ao primeiro n se torna maior do que 1,000,000 (T(1,000,000) = 1,000,0003= 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
quanto
e dizer que o algoritmo possui complexidade de tempo na ordem de n2. 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.Thomas H. Cormen et al., 2001, Introduction to Algorithms, Second Edition
Assintótico Infinitesimal -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 -grande. Considere, por exemplo, série exponencial e duas expressões dela que são válidas quando é pequeno:
A segunda expressão (a que possui ) representa que o valor absoluto do erro é menor do que alguns tempos constantes quando é 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
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(nc) e O(cn) 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 nc para qualquer c é chamada superpolinomial. Uma que cresce mais devagar que qualqrue função exponencial na forma cn é 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 nlog n.
Nós podemos ignorar quaisquer potências de n dentro de logaritmos. O conjunto O(log n) é exatamente o mesmo que O(log(nc)). Os logaritmos diferem apenas de um fator constante (já que log(nc) = 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, 2n e 3n 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 n2, substituir o n por cn significa que o algoritmo roda na ordem de c2n2, e a notação O-grande ignora a constante c2. Isso pode ser escrito como c2n2 = O(n2). Se, no entanto, um algoritmo roda na ordem de 2n, substituir n por cn nos dá 2cn = (2c)n. Isso não é equivalente a 2n 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
Soma
Isso implica que , que significa que é um cone convexo. Se f e g são funções positivas,
Multiplicação por uma constante Seja k uma constante. Então: se k é diferente de zero.
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 e são duas funções definidas em um subconjunto de . Nós dizemos que
se somente se
Equivalentemente, a condição em que para algum pode ser substituída pela condição em que , onde denota a Distância de Chebyshev. Por exemplo, a sentença
afirma que existem constantes C e M tal que
onde g(n,m) é definido por
Note que essa definição permite a todas as coordenadas de incrementar o infinito. Em particular, a sentença
(i.e., ) é bem diferente de
(i.e., ).
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.
Questões de notação Sinal de igualdade 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(x2) é verdade, porém O(x2) = O(x) não é. 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 = n2 das identidades n = O(n2) e n2 = O(n2)." 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. 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." (Unabridged version)
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,
expressa o mesmo que
Exemplo