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 $\Omega(f(n))$\Omega, left parenthesis, f, left parenthesis, n, right parenthesis, right parenthesis, entonces para una $n$n suficientemente grande, el tiempo de ejecución es por lo menos $k \cdot f(n)$k, dot, f, left parenthesis, n, right parenthesis para alguna constante $k$k. Aquí está cómo pensar acerca de un tiempo de ejecución que es $\Omega(f(n))$\Omega, left parenthesis, f, left parenthesis, n, right parenthesis, right parenthesis:

Decimos que el tiempo de ejecución es "Ω grande de $f(n)$f, left parenthesis, n, right parenthesis". 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 $\Theta(f(n))$\Theta, left parenthesis, f, left parenthesis, n, right parenthesis, right parenthesis automáticamente implica $O(f(n))$O, left parenthesis, f, left parenthesis, n, right parenthesis, right parenthesis, también automáticamente implica $\Omega(f(n))$\Omega, left parenthesis, f, left parenthesis, n, right parenthesis, right parenthesis. Así que podemos decir que el tiempo de ejecución del peor caso de la búsqueda binaria es $\Omega(\log_2 n)$\Omega, left parenthesis, log, start base, 2, end base, n, right parenthesis.

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 $\Omega(1)$\Omega, left parenthesis, 1, right parenthesis, 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 $\Omega$\Omega grande, $O$O grande y $\Theta$\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.