MAC0338   Análise de Algoritmos

Notação O, Omega e Theta

A análise de algoritmos precisa de um tipo estranho de matemática que confunde

n²   com   (3/2)n²   com   9999n²   com   n²/1000   com   n²+100n   etc.

Esse tipo de matemática é "assintótico" (pois está interessado somente em valores grandes de n). Nessa matemática, as funções são classificadas em "ordens" (como as ordens religiosas que apareceram na Europa durante a Idade Média); todas as funções de uma mesma ordem são "equivalentes". As cinco funções acima, por exemplo, pertencem à mesma ordem.

Ordem O

Antes de dar uma definição do conceito de ordem, 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 n₀ tal que f(n) >= 0 para todo n maior que n₀.)

DEFINIÇÃO BÁSICA: Dadas funções assintoticamente não-negativas f e g, dizemos que f está na ordem O de g,  e escrevemos f = O(g),  se

0   <=   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 n₀ tais que f(n) <= c · g(n) para todo n maior que n₀.

EXEMPLO: Se f(n) <= 9999 g(n) para todo n >= 1000 então f = O(g).  (Mas cuidado: a recíproca não é verdadeira!)

EXEMPLO: Suponha que f(n) = (3/2)n² + (7/2)n - 4 e que g(n) = n². A tabela abaixo sugere que f(n) <= 2g(n) para n >= 6 e portanto parece que f(n) = O(g(n)).

                          n      f(n)   g(n) 
                          0       -4      0
                          1        1      1
                          2        9      4
                          3       20      9
                          4       34     16
                          5       51     25
                          6       71     36
                          7       94     49
                          8      120     64

É fácil verificar que, de fato, f(n) = O(g(n)) com um cálculo mais grosseiro: f(n) <= 2n² + 4n² = 6n² = 6g(n) para todo n.

Exercícios

1. Quais das conjecturas abaixo são verdadeiras? Justifique.

   10n = O(n)           10n² = O(n)           10n⁵⁵ = O(2ⁿ)

2. É verdade que  n² + 200n + 300   =   O(n²) ?  Justifique.  [Solução]
   
   
3. É verdade que  n² - 200n - 300   =   O(n) ?  Justifique.  [Solução]
   
   
4. Quais das conjecturas abaixo são verdadeiras? Justifique.

   (3/2)n² + (7/2)n - 4 = O(n)           (3/2)n² + (7/2)n - 4 = O(n²)          

5. É verdade que  n³-999999n²-1000000 = O(n²) ? Justifique.
   
   
6. Quais das conjecturas abaixo são verdadeiras? Justifique.

   log₂n = O(log₃n)           log₃n = O(log₂n)

7. É verdade que    teto(lg(n))   =   O(lg(n))  ?  Justifique.  [Solução]

Ordem "Omega" e ordem "Theta"

A expressão "f = O(g)" tem o mesmo sabor que "f <= g". Agora precisamos de um conceito que tenha o sabor de "f >= g" e de um conceito que tenha o sabor de "f = g".

DEFINIÇÃO 2: Dadas funções assintoticamente não-negativas f e g, dizemos que f está na ordem Omega (veja dicionário) de g,  e escrevemos  f = Omega(g),  se

f(n)   >=   c · g(n)   >=   0

para algum c positivo e para todo n suficientemente grande. Em outras palavras, existe um número positivo c e um número n₀ tais que f(n) >= c · g(n) para todo n maior que n₀.

EXEMPLO: Se f(n) >= g(n)/100000 para todo n >= 888 então f = Omega(g).  (Mas cuidado: a recíproca não é verdadeira!)

Qual a relação entre O e Omega? Não é difícil verificar que f = O(g) se e somente se g = Omega(f).

DEFINIÇÃO 3: Dizemos que f e g estão na mesma ordem Theta (veja dicionário) e escrevemos f = Theta(g) se

f = O(g)   e   f = Omega(g).

Trocando em miúdos, f = Theta(g) significa que c₁g(n) <= f(n) <= c₂g(n) para algum c₁ positivo, algum c₂ positivo, e para todo n suficientemente grande.

EXEMPO:   As funções abaixo pertencem todas à ordem Theta(n²):

n²   ,    (3/2)n²   ,    9999n²   ,    n²/1000   ,    n²+100n .

Exercício

Quais das conjecturas abaixo são verdadeiras? Justifique.

1.     (3/2)n² + (7/2)n - 4 = Theta(n²)
2.     9999 n² = Theta(n²)
3.     n²/1000 - 999n = Theta(n²)
4.     log₂n + 1 = Theta(log₁₀n)