Cuando usamos notación asintótica para expresar la tasa de crecimiento del tiempo de ejecución de un algoritmo en términos del tamaño de la entrada n, es bueno tener algunas cosas en mente.
Empecemos con algo sencillo. Supón que el algoritmo se tardó una cantidad constante de tiempo, sin importar el tamaño de su entrada. Por ejemplo, si te dieron un arreglo que ya está ordenado en orden ascendente y tienes que encontrar el elemento mínimo, te tomaría un tiempo constante, ya que el elemento mínimo debe estar en el índice 0. Como queremos usar una función de n en notación asintótica, podrías decir que este algoritmo se ejecuta en un tiempo Θ(n0) \Theta(n^0) . ¿Por qué? Porque n, start superscript, 0, end superscript, equals, 1 y el tiempo de ejecución del algoritmo está dentro del rango de un factor constante de 1. Sin embargo, en la práctica, no escribimos Θ(n0) \Theta(n^0) ; escribimos Θ(1) \Theta(1) .
Ahora supón que un algoritmo se tardó un tiempo Θ(log10n) \Theta(\log_{10} n) . También puedes decir que se tardó un tiempo Θ(lgn) \Theta(\lg n) (eso es, un tiempo Θ(log2n) \Theta(\log_2 n) ). Siempre que la base del logaritmo sea una constante, no importa qué base usemos en la notación asintótica. ¿Por qué no? Porque hay una fórmula matemática que dice
log, start subscript, a, end subscript, n, equals, start fraction, log, start subscript, b, end subscript, n, divided by, log, start subscript, b, end subscript, a, end fraction
para todos los números positivos a, b y n. Por lo tanto, si a y b son constantes, entonces log, start subscript, a, end subscript, n y log, start subscript, b, end subscript, n difieren solo por un factor de log, start subscript, b, end subscript, a y ese es un factor constante que podemos ignorar en la notación asintótica.
Por lo tanto, podemos decir que el tiempo de ejecución del peor caso de una búsqueda binaria es Θ(logan) \Theta(\log_a n) para cualquier constante positiva a. ¿Por qué? El número de intentos es a lo más lgn+1 \lg n + 1 , generar y probar cada intento toma un tiempo constante, y configurar y regresar toma un tiempo constante. Como una cuestión práctica, escribimos que una búsqueda binaria se tarda un tiempo Θ(lgn) \Theta(\lg n) porque a los computólogos les gusta pensar en potencias de 2 (y escribimos menos caracteres que si escribiéramos Θ(log2n) \Theta(\log_2 n) ).
Hay un orden en las funciones que a menudo vemos cuando analizamos algoritmos usando notación asintótica. Si a y b son constantes y a, is less than, b, entonces un tiempo de ejecución de Θ(na) \Theta(n^a) crece más despacio que un tiempo de ejecución de Θ(nb) \Theta(n^b) . Por ejemplo, un tiempo de ejecución de Θ(n) \Theta(n) , que es Θ(n1) \Theta(n^1) , crece más despacio que un tiempo de ejecución de Θ(n2) \Theta(n^2) . Los exponentes tampoco tienen que ser enteros. Por ejemplo, un tiempo de ejecución de Θ(n2) \Theta(n^2) crece más despacio que un tiempo de ejecución de Θ(n2n) \Theta(n^2 \sqrt{n}) , que es Θ(n2.5) \Theta(n^{2.5}) .
Los logaritmos crecen más despacio que los polinomios. Eso es, Θ(lgn) \Theta(\lg n) crece más despacio que Θ(na) \Theta(n^a) para cualquier constante positiva a. Pero como el valor de lgn \lg n crece a medida que n crece, Θ(lgn) \Theta(\lg n) crece más rápido que Θ(1) \Theta(1) .
Aquí hay una lista de funciones en notación asintótica que a menudo encontramos cuando analizamos algoritmos, listadas de la que crece más despacio a la que crece más rápido. Esta lista no es exhaustiva; hay muchos más algoritmos cuyos tiempos de ejecución no aparecen aquí:
  1. Θ(1) \Theta(1)
  2. Θ(lgn) \Theta(\lg n)
  3. Θ(n) \Theta(n)
  4. Θ(nlgn) \Theta(n \lg n)
  5. Θ(n2) \Theta(n^2)
  6. Θ(n2lgn) \Theta(n^2 \lg n)
  7. Θ(n3) \Theta(n^3)
  8. Θ(2n) \Theta(2^n)
Observa que la función exponencial a, start superscript, n, end superscript, donde a, is greater than, 1, crece más rápido que cualquier función polinomial n, start superscript, b, end superscript, donde b es cualquier constante.

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.