Veamos una implementación sencilla de una búsqueda lineal:
var doLinearSearch = function(array, targetValue) {
  for (var guess = 0; guess < array.length; guess++) {
    if (array[guess] === targetValue) { 
        return guess;  // ¡lo encontraste!
    }
  }
  return -1;  // no lo encontraste
};
Vamos a denotar el tamaño del arreglo (array.length) por n n . El número máximo de veces que se puede ejecutar el bucle for es n n , y este caso peor ocurre cuando el valor que se está buscando no está presente en el arreglo.
Cada vez que el bucle for itera, tiene que hacer varias cosas:
  • comparar guess con array.length
  • compara array[guess] con targetValue
  • posiblemente regresar el valor de guess
  • incrementar guess.
Cada uno de estos pequeños cálculos toma una cantidad constante de tiempo cada vez que se ejecuta. Si el bucle for iterara n n veces, entonces el tiempo para todas las n n iteraciones es c1n c_1 \cdot n , donde c1 c_1 es la suma de los tiempos para los cálculos en una iteración del bucle. Ahora, aquí no podemos decir cuál es el valor de c1 c_1 , porque depende de la velocidad de la computadora, el lenguaje de programación utilizado, el compilador o intérprete que traduce la fuente del programa fuente en código ejecutable y otros factores.
Este código tiene un poco de encabezado: para crear el bucle for (incluyendo inicializar guess a 0) y posiblemente regresar -1 al final. Llamemos al tiempo para este encabezado c2 c_2 , que también es una constante. Por lo tanto, el tiempo total de la búsqueda lineal en el peor de los casos es de c1n+c2 c_1 \cdot n + c_2 .
Como ya lo argumentamos, el factor constante c1 c_1 y el término de orden inferior c2 c_2 no nos dicen nada acerca de la tasa de crecimiento del tiempo de ejecución. Lo que es significativo es que el tiempo de ejecución de una búsqueda lineal en el peor caso crece como el tamaño del arreglo n n . La notación que usamos para este tiempo de ejecución es Θ(n) \Theta(n) . Esa es la letra griega "theta," y decimos "Theta grande de n n " o simplemente "Theta de n n ".
Cuando decimos que un tiempo de ejecución particular es de Θ(n) \Theta(n) , estamos diciendo que una vez que n n sea suficientemente grande, el tiempo de ejecución será por lo menos k1n k_1 \cdot n y a lo más k2n k_2 \cdot n para algunas constantes k1 k_1 y k2 k_2 . Aquí está cómo pensar acerca de Θ(n) \Theta(n) :
Para valores pequeños de n n , no nos importa cómo se compara el tiempo de ejecución con k1n k_1 \cdot n o k2n k_2 \cdot n . Pero una vez que n n se hace suficientemente grande, sobre o a la derecha de la línea punteada, el tiempo de ejecución debe estar entre k1n k_1 \cdot n y k2n k_2 \cdot n . Mientra existan estas constantes k1 k_1 y k2 k_2 , decimos que el tiempo de ejecución es Θ(n) \Theta(n) .
No estamos restringidos a solo n n en la notación Θ grande. Podemos usar cualquier función, como n2 n^2 , nlog2n n \log_2 n , o cualquier otra función de n n . Aquí está cómo pensar acerca del tiempo de ejecución que es Θ(f(n)) \Theta(f(n)) para alguna función f(n) f(n) :
Una vez que n n se hace suficientemente grande, el tiempo de ejecución está entre k1f(n) k_1 \cdot f(n) y k2f(n) k_2 \cdot f(n) .
En la práctica, simplemente descartamos factores constantes y términos de orden inferior. Otra ventaja de usar la notación Θ grande es que no tenemos que preocuparnos por las unidades de tiempo que estamos usando. Por ejemplo, supón que calculas que un tiempo de ejecución es de 6n2+100n+300 6n^2 + 100n + 300 microsegundos. O tal vez sean milisegundos. Cuando usas la notación Θ grande, no lo especificas. También descartas el factor 6 y los términos de orden inferior 100n+300 100n + 300 , y solo dices que el tiempo de ejecución es de Θ(n2) \Theta(n^2) .
Cuando usamos la notación Θ grande, estamos diciendo que tenemos una cota asintóticamente ajustada sobre el tiempo de ejecución. "Asintóticamente" porque importa solo para valores grandes de n n . "Cota ajustada" porque ajustamos el tiempo de ejecución dentro del rango de una constante hacia arriba y hacia abajo.

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.
Cargando