Estou com dificuldades para conseguir provar se
f(n)=Omega(g(n))
, então g(n) = O(f(n))
.
Como seria essa comprovação?
Com cálculo e com teoria?
Estou com dificuldades para conseguir provar se
f(n)=Omega(g(n))
, então g(n) = O(f(n))
.
Como seria essa comprovação?
Com cálculo e com teoria?
Considerando O como limite superior de F(n)
Considerando Omega como limite inferior de G(n)
Temos:
F(n) = Omega (G(n)) -> F(n) <= G(n)
G(n) = O(F(n)) -> G(n) >= F(n)
F(n) <= G(n) <=> G(n) >= F(n)
Logo F(n) <= G(n)
equivale a G(n) >= F(n)