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 $\Theta(\log_2 n)$\Theta, left parenthesis, log, start base, 2, end base, n, right parenthesis, sería incorrecto decir que búsqueda binaria se ejecuta en un tiempo $\Theta(\log_2 n)$\Theta, left parenthesis, log, start base, 2, end base, n, right parenthesis en todos los casos. ¿Qué pasa si encontramos el valor objetivo después del primer intento? Entonces se ejecuta en un tiempo $\Theta(1)$\Theta, left parenthesis, 1, right parenthesis. El tiempo de ejecución de la búsqueda binaria nunca es peor que $\Theta(\log_2 n)$\Theta, left parenthesis, log, start base, 2, end base, n, right parenthesis, 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))$O, left parenthesis, f, left parenthesis, n, right parenthesis, right parenthesis, entonces para $n$n suficientemente grande, el tiempo de ejecución es a lo más $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 $O(f(n))$O, left parenthesis, f, left parenthesis, n, right parenthesis, right parenthesis:

Decimos que el tiempo de ejecución es "O grande de $f(n)$f, left parenthesis, n, right parenthesis" o simplemente "O de $f(n)$f, left parenthesis, n, right parenthesis". 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)$O, left parenthesis, log, start base, 2, end base, n, right parenthesis. Podemos hacer una afirmación más fuerte acerca del peor caso del tiempo de ejecución: es $\Theta(\log_2 n)$\Theta, left parenthesis, log, start base, 2, end base, n, right parenthesis. 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)$O, left parenthesis, log, start base, 2, end base, n, right parenthesis.

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 $\Theta(f(n))$\Theta, left parenthesis, f, left parenthesis, n, right parenthesis, right parenthesis en una situación particular, entonces también es $O(f(n))$O, left parenthesis, f, left parenthesis, n, right parenthesis, right parenthesis. Por ejemplo, podemos decir que como el tiempo de ejecución del peor caso de una búsqueda binaria es $\Theta(\log_2 n)$\Theta, left parenthesis, log, start base, 2, end base, n, right parenthesis, también es $O(\log_2 n)$O, left parenthesis, log, start base, 2, end base, n, right parenthesis.

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)$O, left parenthesis, log, start base, 2, end base, n, right parenthesis pero no siempre se ejecuta en un tiempo $\Theta(\log_2 n)$\Theta, left parenthesis, log, start base, 2, end base, n, right parenthesis.

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)$O, left parenthesis, n, right parenthesis. Eso es porque el tiempo de ejecución crece no más rápido que una constante multiplicada por $n$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)$O, left parenthesis, n, right parenthesis 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, left parenthesis, n, squared, right parenthesis, $O(n^3)$O, left parenthesis, n, cubed, right parenthesis y $O(2^n)$O, left parenthesis, 2, start superscript, n, end superscript, right parenthesis. Pero, en cualquier caso, ninguna de $\Theta(n)$\Theta, left parenthesis, n, right parenthesis, $\Theta(n^2)$\Theta, left parenthesis, n, squared, right parenthesis, $\Theta(n^3)$\Theta, left parenthesis, n, cubed, right parenthesis ni $\Theta(2^n)$\Theta, left parenthesis, 2, start superscript, n, end superscript, right parenthesis 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.