## 1.2.3 NOTACIÓN OMEGA

Existe una notación para indicar la mínima cantidad de recursos que un algoritmo necesita para alguna clase de entrada. La cota inferior de un algoritmo, denotada por el símbolo Ω, pronunciado “Gran Omega” u “Omega”, tiene la siguiente definición:

T(n) está en el conjunto Ω(g(n)), si existen dos constantes positivas c y n0 tales que |T(n)| ≥ c|g(n)| para todo n > n0. •

Ejemplo: Si T(n)=c1n2+c2n para c1 y c2 > 0, entonces: |c1n2 +c2n| ≥ |c1 n2 | ≥ c1|n2 | Por lo tanto, T(n) está en Ω(n2 ).

Ω Es el reverso de O.
f (x ) = Ω(g (x )) -><- g (x ) = O (f (x ))

Ω Grande dice que asintóticamente f (x ) domina a g (x ).

###