Notación Omega grande (Big-Ω)

A veces, queremos decir que un algoritmo toma por lo menos una cierta cantidad de tiempo, sin dar una cota superior. Utilizamos la notación Ω grande; esa es la letra griega "omega".

Si un tiempo de ejecución es $\mathrm{\Omega }(f(n))$‍, entonces para una $n$‍ suficientemente grande, el tiempo de ejecución es por lo menos $k\cdot f(n)$‍ para alguna constante $k$‍. Aquí está cómo pensar acerca de un tiempo de ejecución que es $\mathrm{\Omega }(f(n))$‍:

Decimos que el tiempo de ejecución es "Ω grande de $f(n)$‍". Usamos la notación Ω grande para límites asintóticos inferiores, ya que acota el crecimiento del tiempo de ejecución por abajo para entradas de tamaños suficientemente grandes.

Así como $\mathrm{\Theta }(f(n))$‍ automáticamente implica $O(f(n))$‍, también automáticamente implica $\mathrm{\Omega }(f(n))$‍. Así que podemos decir que el tiempo de ejecución del peor caso de la búsqueda binaria es $\mathrm{\Omega }({\log }_{2}n)$‍.

También podemos hacer afirmaciones correctas, pero imprecisas, al usar la notación Ω grande. Por ejemplo, si en verdad tienes un millón de pesos en el bolsillo, ciertamente podrías decir "tengo una cantidad de dinero en mi bolsillo y es por lo menos de 10 pesos". Eso es correcto, pero ciertamente no muy preciso. Del mismo modo, podemos decir de manera correcta pero imprecisa que el tiempo de ejecución del peor caso de la búsqueda binaria es $\mathrm{\Omega }(1)$‍, porque sabemos que tarda por lo menos un tiempo constante.

Por supuesto, típicamente, cuando hablamos acerca de los algoritmos, tratamos de describir sus tiempos de ejecución lo más precisos posibles. Aquí proporcionamos ejemplos de afirmaciones imprecisas para ayudarte a entender mejor $\mathrm{\Omega }$‍ grande, $O$‍ grande y $\mathrm{\Theta }$‍ grande.

Este contenido es una colaboración de los profesores de Dartmouth Computer Science Thomas Cormen y Devin Balkcom, con el equipo de contenidos de computación de Khan Academy. El contenido está bajo licencia CC-BY-NC-SA.