Similar a la notación O grande, la función Omega grande (Ω) se usa en ciencias de la computación para describir el desempeño o la complejidad de un algoritmo.
Si un tiempo de ejecución es Ω (f (n)), entonces para n suficientemente grande, el tiempo de ejecución es al menos k⋅f (n) para alguna constante k. He aquí cómo pensar en un tiempo de ejecución que es Ω (f (n)):
Decimos que el tiempo de ejecución es "gran-Ω de f (n)". Usamos la notación de Ω grande para los límites inferiores asintóticos , ya que limita el crecimiento del tiempo de ejecución desde abajo para tamaños de entrada lo suficientemente grandes.
Diferencia entre Big O y Big Ω
La diferencia entre la notación Big O y la notación Big Ω es que Big O se usa para describir el peor tiempo de ejecución de un algoritmo. Pero, la notación Big Ω, por otro lado, se usa para describir el mejor tiempo de ejecución para un algoritmo dado.
Más información:
- Notación Big-Ω (Big-Omega)
