O que significa dizer que uma função g(n) é Omega(f(n)) ?

Passo 1

O enunciado diz: queremos entender o significado de afirmar que uma função g(n) é Omega(f(n)). O conteúdo é notação assintótica, mais precisamente o limite inferior (lower bound).

Passo 2

Para definir formalmente g(n) = Omega(f(n)), usamos: existem constantes c > 0 e n0 >= 1 tais que, para todo n >= n0, temos
g(n) >= c cdot f(n)
Em outras palavras, a notação Omega(f(n)) diz que g(n) cresce, a longo prazo, no mínimo tão rápido quanto f(n) multiplicada por uma constante positiva.

Passo 3

Por exemplo, se f(n)=n e g(n)=3n+5, podemos escolher c=1 e n0=5, pois para todo n>=5 temos 3n+5>= n. Assim, 3n+5=Omega(n).

Resposta

Dizer que g(n)=Omega(f(n)) significa que existem constantes c>0 e n0 tais que, para todo n>= n0, vale
g(n)>= c,f(n)

Exercícios relacionados