Notação Omega

---

A notação assintótica $\Omega$ (Omega) é usada na análise de algoritmos para descrever um limite inferior do crescimento de uma função à medida que o tamanho da entrada $n$ aumenta. Enquanto a Notação Big O estabelece um limite superior, a notação $\Omega$ define o comportamento mínimo, ou seja, ela nos diz que o tempo de execução de um algoritmo não será menor do que uma certa taxa de crescimento (crescimento mínimo).

Definição Formal

Para uma função $g(n)$, o conjunto de funções $\Omega (g(n))$ é definido como:

$$\Omega (g(n))=\{f(n):\exists c>0\text{ e }{n}_0>0\text{ tal que }f(n)\ge c\cdot g(n),\forall n\ge n_0\}$$

Isso significa que, após um determinado valor $n_0$, a função $f(n)$ sempre cresce pelo menos tão rápido quanto $g(n)$, multiplicada por uma constante $c$. Ou seja, $g(n)$ serve como um limite inferior assintótico para o crescimento de $f(n)$.

Interpretação

A notação $\Omega (g(n))$ nos informa o crescimento mínimo de uma função. Se $f(n)=\Omega (g(n))$, então, para entradas suficientemente grandes, a função $f(n)$ cresce pelo menos tão rápido quanto $g(n)$, a partir de algum valor $n_0$.

Exemplo: Verificar se $n\log n=\Omega (n)$

Queremos verificar se $n\log n\ge c\cdot n$ para algum $c>0$. Aplicando a definição:

$$c\cdot n\le n\log n$$

Podemos simplificar:

$$c\le \log n$$

Essa desigualdade é verdadeira para valores grandes de $n$, tomando $c=1$ e $n_0=2$, pois $\log n$ aumenta conforme $n$ cresce. Logo, podemos afirmar que:

$$n\log n=\Omega (n)$$

Isso significa que, para valores grandes de $n$, $n\log n$ cresce pelo menos tão rápido quanto $n$.

Referências

---

Aula 2 - Análise de algoritmos