Ao ver uma expressão como n+10 ou n²+1, a maioria das pessoas pensa automaticamente em valores pequenos de n, valores próximos de zero. A análise de algoritmos faz exatamente o contrário: ignora os valores pequenos e concentra-se nos valores enormes de n. Para valores enormes de n, as funções
n2 , (3/2)n2 , 9999n2 , n2/1000 , n2+100n , etc.
crescem todas com a mesma velocidade e portanto são todas "equivalentes". Esse tipo de matemática, interessado somente em valores enormes de n, é chamado assintótico. Nessa matemática, as funções são classificadas em "ordens" (como as ordens religiosas da Idade Média); todas as funções de uma mesma ordem são "equivalentes". As cinco funções acima, por exemplo, pertencem à mesma ordem.
Veja o verbete Big O notation na Wikipedia.
Convém restringir a atenção a funções assintoticamente não negativas, ou seja, funções f tais que f(n) ≥ 0 para todo n suficientemente grande. Mais explicitamente: f é assintoticamente não negativa se existe n0 tal que f(n) ≥ 0 para todo n maior que n0. Agora podemos definir a ordem Ο. [Esta letra é um O maiúsculo. Ou melhor, um ômicron grego maiúsculo, como quer Knuth.]
Definição: Dadas funções assintoticamente não negativas f e g, dizemos que f está na ordem Ο de g e escrevemos f = Ο(g) se f(n) ≤ c · g(n) para algum c positivo e para todo n suficientemente grande. Em outras palavras, existe um número positivo c e um número n0 tais que f(n) ≤ c · g(n) para todo n maior que n0.
(A notação "Ο(∗)" empregada nesta definição é conhecida como notação assintótica ou notação de Landau.)
Exemplo 1: Se f(n) ≤ 9999 g(n) para todo n ≥ 1000 então f = Ο(g). (Cuidado: a recíproca não é verdadeira!)
Exemplo 2: Suponha que f(n) = 2n² + 3n + 4 e g(n) = n². Observe que
2n2 + 3n + 4 ≤ 2n2 + 3n2 + 4n2 = 9n2
desde que n ≥ 1. Resumindo, f(n) ≤ 9 g(n) para todo n ≥ 1. Portanto, f(n) = Ο(g(n)).
Exemplo 3: Suponha que f(n) = 3 + 2/n e que g(n) = n0, ou seja, g(n) = 1. Então
3 + 2/n ≤ 3 + 1 = 4 = 4n0
desde que n ≥ 2. Resumindo, f(n) ≤ 4 g(n) para todo n ≥ 2. Portanto, f(n) = Ο(g(n)).
Exemplo 4: Suponha que f(n) = n3 e que g(n) = 200n2. Não é verdade que f(n) = Ο(g(n)). De fato, se existissem c e n0 tais que f(n) ≤ c g(n), teríamos
n ≤ 200c
para todo n ≥ n0. Mas isso é absurdo!
A expressão "f = Ο(g)" tem o mesmo sabor que "f ≤ g". Agora precisamos de um conceito que tenha o sabor de "f ≥ g".
Definição: Dadas funções assintoticamente não negativas f e g, dizemos que f está na ordem Omega de g e escrevemos f = Ω(g) se f(n) ≥ c · g(n) para algum c positivo e para todo n suficientemente grande. Em outras palavras, existe um número positivo c e um número n0 tais que f(n) ≥ c · g(n) para todo n maior que n0.
Exemplo: Se f(n) ≥ g(n)/100000 para todo n ≥ 888 então f = Ω(g). (Cuidado: a recíproca não é verdadeira!)
Qual a relação entre Ο e Ω? Não é difícil verificar que f = Ο(g) se e somente se g = Ω(f).
Além dos conceitos que têm o sabor de "f ≤ g" e de "f ≥ g", precisamos de um que tenha o sabor de "f = g".
Definição: Dizemos que f e g estão na mesma e escrevemos f = Θ(g) se f = Ο(g) e f = Ω(g). Trocando em miúdos, f = Θ(g) significa que existe números positivos c e d tais que c g(n) ≤ f(n) ≤ d g(n) para todo n suficientemente grande.
Exemplo: As funções abaixo pertencem todas à ordem Θ(n2):
n2 , (3/2)n2 , 9999n2 , n2/1000 , n2+100n .
A discussão acima supõe, implicitamente, que todas as funções estão definidas no conjunto dos números naturais. Mas tudo continua funcionando se as funções estiverem definidas em algum outro domínio. Eis alguns exemplos de domínios:
A mesma notação Ο é usada para todos os domínios. Por exemplo, se f é uma função assintoticamente não negativa definida nas potências inteiras de 2, dizer que f(n) = Ο(n2) é o mesmo que dizer que existe um número positivo c tal que f(n) ≤ c n2 para todo n da forma 2k com k suficientemente grande.
As mesmas observações se aplicam à notação Ω e à notação Θ.