Usamos la notación Θ grande para acotar de manera asintótica el crecimiento de un tiempo de ejecución dentro del rango 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 una búsqueda binaria sea Θ(lgn) \Theta(\lg n) , sería incorrecto decir que la búsqueda binaria se ejecuta en un tiempo Θ(lgn) \Theta(\lg n) en todos los casos. ¿Qué pasa si encontramos el valor objetivo en el primer intento? Entonces se ejecuta en un tiempo Θ(1) \Theta(1) . El tiempo de ejecución de una búsqueda binaria nunca es peor que Θ(lgn) \Theta(\lg n) , pero algunas 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, left parenthesis, f, left parenthesis, n, right parenthesis, right parenthesis, entonces para n suficientemente grande, el tiempo de ejecución es a lo más k, dot, f, left parenthesis, n, right parenthesis para alguna constante k. Aquí está cómo pensar acerca de un tiempo de ejecución que es O, left parenthesis, f, left parenthesis, n, right parenthesis, right parenthesis:
6n^2 vs 100n+300
Decimos que el tiempo de ejecución es "O grande de f, left parenthesis, n, right parenthesis" o simplemente "O de 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(lgn) O(\lg n) . Podemos hacer una afirmación más fuerte acerca del peor caso del tiempo de ejecución: es Θ(lgn) \Theta(\lg 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(lgn) O(\lg n) .
Si regresas a la definición de la notación Θ grande, te darás cuenta de que se parece mucho a la notación O grande, excepto que la notación Θ grande acota al tiempo de ejecución por arriba y por abajo, en vez de solo por arriba. Si decimos que el tiempo de ejecución es Θ(f(n)) \Theta(f(n)) en una situación en particular, entonces también es O, left parenthesis, f, left parenthesis, n, right parenthesis, right parenthesis. Por ejemplo, podemos decir que como el peor caso del tiempo de ejecución de una búsqueda binaria es Θ(lgn) \Theta(\lg n) , también es O(lgn) O(\lg n) . Lo opuesto no es necesariamente cierto: como hemos visto, podemos decir que una búsqueda binaria siempre se ejecuta en un tiempo O(lgn) O(\lg n) pero no que siempre se ejecuta en un tiempo Θ(lgn) \Theta(\lg n) .
Como la notación O grande solamente da una cota asintótica superior, y no una cota asintóticamente ajustada, podemos hacer declaraciones que en primera instancia 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, 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. De hecho, crece más despacio. Piénsalo de esta manera. Supón que tienes 10 pesos en el bolsillo. Vas con un amigo y le dices: "Tengo una cantidad de dinero en mi bolsillo, y te aseguro que no es más de un millón de pesos". Tu afirmación es absolutamente cierta, aunque no terriblemente precisa. Un millón de pesos es una cota superior de los 10 pesos, del mismo modo que O, left parenthesis, n, right parenthesis es una cota superior del tiempo de ejecución de la búsqueda binaria. Otras cotas superiores, imprecisas, sobre la búsqueda binaria serían O, left parenthesis, n, start superscript, 2, end superscript, right parenthesis, O, left parenthesis, n, start superscript, 3, end superscript, right parenthesis y O, left parenthesis, 2, start superscript, n, end superscript, right parenthesis. Pero en cualquier caso, ninguna de Θ(n) \Theta(n) , Θ(n2) \Theta(n^2) , Θ(n3) \Theta(n^3) ni Θ(2n) \Theta(2^n) serían correctas para describir el tiempo de ejecución de una 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.