Notación O grande (Big-O)

Usamos la notación Θ grande para acotar de manera asintótica el crecimiento de un tiempo de ejecución a que esté dentro de factores constantes por arriba y por abajo. A veces queremos acotar solo por arriba.

Por ejemplo, aunque el peor tiempo de ejecución de la búsqueda binaria es $\mathrm{\Theta }({\log }_{2}n)$‍, sería incorrecto decir que búsqueda binaria se ejecuta en un tiempo $\mathrm{\Theta }({\log }_{2}n)$‍ en todos los casos. ¿Qué pasa si encontramos el valor objetivo después del primer intento? Entonces se ejecuta en un tiempo $\mathrm{\Theta }(1)$‍. El tiempo de ejecución de la búsqueda binaria nunca es peor que $\mathrm{\Theta }({\log }_{2}n)$‍, pero a veces es mejor.

Sería conveniente tener una forma de notación asintótica que signifique "el tiempo de ejecución crece a lo más por este tanto, pero puede crecer más lentamente". Usamos la notación "O grande" justo para estas ocasiones.

Si un tiempo de ejecución es $O(f(n))$‍, entonces para $n$‍ suficientemente grande, el tiempo de ejecución es a lo más $k\cdot f(n)$‍ para alguna constante $k$‍. Aquí está cómo pensar acerca de un tiempo de ejecución que es $O(f(n))$‍:

Decimos que el tiempo de ejecución es "O grande de $f(n)$‍" o simplemente "O de $f(n)$‍". Usamos la notación O grande para cotas superiores asintóticas, ya que acota el crecimiento del tiempo de ejecución por arriba para entradas suficientemente grandes.

Ahora tenemos una manera de caracterizar el tiempo de ejecución de la búsqueda binaria en todos los casos. Podemos decir que el tiempo de ejecución de una búsqueda binaria siempre es $O({\log }_{2}n)$‍. Podemos hacer una afirmación más fuerte acerca del peor caso del tiempo de ejecución: es $\mathrm{\Theta }({\log }_{2}n)$‍. Pero para una afirmación que cubra todos los casos, la afirmación más fuerte que podemos hacer es que la búsqueda binaria se ejecuta en un tiempo $O({\log }_{2}n)$‍.

Si regresamos a la definición de la notación de Θ grande, te darás cuenta de que se parece mucho a la notación O grande, excepto que la notación Θ grande acota el tiempo de ejecución tanto por arriba como por abajo, en lugar de solo por arriba. Si decimos que un tiempo de ejecución es $\mathrm{\Theta }(f(n))$‍ en una situación particular, entonces también es $O(f(n))$‍. Por ejemplo, podemos decir que como el tiempo de ejecución del peor caso de una búsqueda binaria es $\mathrm{\Theta }({\log }_{2}n)$‍, también es $O({\log }_{2}n)$‍.

Lo inverso no es necesariamente cierto: como hemos visto, podemos decir que la búsqueda binaria siempre se ejecuta en un tiempo $O({\log }_{2}n)$‍ pero no siempre se ejecuta en un tiempo $\mathrm{\Theta }({\log }_{2}n)$‍.

Como la notación O grande solo da una cota asintótica superior, y no una cota superior asintóticamente ajustada, podemos hacer afirmaciones que a primera vista parecen incorrectas, pero que son técnicamente correctas. Por ejemplo, es absolutamente correcto decir que la búsqueda binaria se ejecuta en un tiempo $O(n)$‍. Eso es porque el tiempo de ejecución crece no más rápido que una constante multiplicada por $n$‍. De hecho, crece más lento.

Piénsalo de esta manera. Supón que tienes 10 pesos en el bolsillo. Vas con tu amigo y le dices: "tengo una cantidad de dinero en mi bolsillo, y te garantizo que no es más de 1 millón de pesos". Tu afirmación es totalmente cierta, aunque no muy precisa.

1 millón de pesos es una cota superior de los 10 pesos, así como $O(n)$‍ es una cota superior del tiempo de ejecución de la búsqueda binaria. Otras cotas superiores, imprecisas, de una búsqueda binaria serían $O(n^2)$‍, $O(n^3)$‍ y $O(2^n)$‍. Pero, en cualquier caso, ninguna de $\mathrm{\Theta }(n)$‍, $\mathrm{\Theta }(n^2)$‍, $\mathrm{\Theta }(n^3)$‍ ni $\mathrm{\Theta }(2^n)$‍ serían correctas para describir el tiempo de ejecución de la búsqueda binaria.

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.