Notação O, Ω e Θ

A notação assintótica descreve como o custo cresce quando n vai ao infinito, ignorando constantes e termos menores. As definições formais:

f ∈ O(g)  ⇔  ∃c>0, n₀ : f(n) ≤ c·g(n) para todo n ≥ n₀   (limite superior)
f ∈ Ω(g)  ⇔  ∃c>0, n₀ : f(n) ≥ c·g(n) para todo n ≥ n₀   (limite inferior)
f ∈ Θ(g)  ⇔  f ∈ O(g) e f ∈ Ω(g)                          (crescimento exato)

Quando alguém diz “esse algoritmo é O(n²)”, quase sempre quer dizer Θ(n²). O(n²) sozinho só garante que ele não é pior que quadrático.

A hierarquia

1 ≺ log n ≺ √n ≺ n ≺ n log n ≺ n² ≺ n³ ≺ 2ⁿ ≺ n! ≺ nⁿ

Uma regra prática: um computador faz na ordem de 10⁸ operações simples por segundo. Com n = 10⁶, n log n ≈ 2·10⁷ roda em frações de segundo; n² = 10¹² leva horas.

# Θ(n²): compara todos os pares
def tem_duplicata_lento(xs):
    return any(xs[i] == xs[j]
               for i in range(len(xs)) for j in range(i + 1, len(xs)))

# Θ(n) em média: um conjunto com hash
def tem_duplicata(xs):
    return len(set(xs)) != len(xs)