Big O y análisis de algoritmos

El panorama: ¿qué medimos?

Cuando preguntas '¿qué tan rápido es este programa?', la respuesta en segundos no ayuda mucho. Un computador rápido y uno lento dan segundos distintos para el mismo programa. Por eso contamos algo que no cambia: el número de pasos básicos (una comparación, una suma, la lectura de una celda de memoria) en función del tamaño de la entrada, que llamamos n.

Dos tipos de costo

Palabras que encontrarás

• Tamaño de la entrada (n): cuántos datos recibe el algoritmo, por ejemplo el número de elementos de una lista.
• [[Asintótico|lo que ocurre cuando n se vuelve muy, muy grande]]: miramos el panorama general para entradas enormes e ignoramos pequeños detalles.
• Orden de crecimiento: la 'forma' del crecimiento, como 'línea recta' o 'curva que se dispara'.
• Peor, mejor y caso promedio: el costo para la entrada más desafortunada, la más afortunada y una entrada típica.
• Cota inferior: un límite que dice 'ningún algoritmo puede hacerlo mejor que esto'.

Crecimiento de funciones y su ordenamiento

Los algoritmos distintos crecen de formas distintas. Algunos casi no notan una entrada más grande. Otros explotan. Para compararlos usamos una pequeña familia de 'velocidades', de la más suave a la más salvaje.

El orden es: 1 < log n < √n < n < n log n < n² < n³ < 2ⁿ < n! < nⁿ. Un 'logaritmo' crece muy despacio: log₂ 1.024 es solo 10, y log₂ 1.000.000 es apenas unos 20.

¿Qué pasa cuando la entrada se duplica?

Dos datos útiles para comparar. Primero, el crecimiento polinomial (una potencia de n, como n² o n^1,5) siempre pierde contra el exponencial (2ⁿ) cuando n es grande. Segundo, una potencia de log n, incluso (log n)¹⁰, siempre pierde contra una pequeña potencia de n como √n cuando n es grande. Así, n log n es menor que n^1,5, porque log n crece más despacio que √n. Y n / log n es menor que n, pero mayor que √n.

Un computador más rápido ayuda menos de lo que crees. Si un algoritmo hace n² operaciones y hoy resuelve n = 1.000 en un segundo, una máquina 100 veces más rápida resuelve solo n = 10.000 en ese segundo (porque 10.000² = 100 × 1.000²). La misma mejora en un algoritmo 2ⁿ suma solo unos 7 a n.

Notación asintótica: O, Ω, Θ, o, ω

Supón que un algoritmo hace exactamente 3n² + 10n + 5 pasos. Para un n enorme, el 10n y el 5 son diminutos al lado de 3n², y el 3 solo depende del computador. Así que decimos que el algoritmo es 'del orden de n²'. Las notaciones de abajo dan una forma precisa de decirlo.

La definición formal (para funciones no negativas)

f(n) = O(g(n)) significa: existen constantes c > 0 y n0 tales que f(n) ≤ c · g(n) para todo n ≥ n0. En palabras: a partir de cierto punto, f nunca pasa de un múltiplo constante de g. Ω es lo mismo con ≥. Θ exige ambas: f = Θ(g) exactamente cuando f = O(g) y f = Ω(g).

Ejemplo: para mostrar que 100n + 50 = O(n), toma c = 150 y n0 = 1. Para n ≥ 1 se tiene 100n + 50 ≤ 100n + 50n = 150n. Otro par válido es c = 101 y n0 = 50. Cualquier par que funcione prueba la afirmación.

Con límites es aún más fácil. Mira la razón f(n)/g(n) cuando n tiende a infinito. Si tiende a 0, entonces f = o(g). Si tiende a infinito, entonces f = ω(g). Si tiende a una constante positiva (por ejemplo 7), entonces f = Θ(g).

razón f(n)/g(n) cuando n -> infinito

  0               ->  f = o(g)     (f es menor)
  constante > 0   ->  f = Θ(g)     (mismo ritmo)
  infinito        ->  f = ω(g)     (f es mayor)

Datos útiles

• n = O(n²) es verdadero. O es solo una cota superior, no tiene que ser ajustada. Es como decir 'tengo menos de 100 años'.
• Ω por sí sola no dice nada sobre una cota superior. 'Esto toma al menos n pasos' puede ser n o 1.000.000 n.
• 2^(n+1) = Θ(2ⁿ), porque 2^(n+1) = 2 · 2ⁿ es solo una constante mayor. Pero 2^(2n) = 4ⁿ = ω(2ⁿ), porque la razón 2ⁿ tiende a infinito.
• La base del logaritmo no importa dentro de O. log₂ n y log₁₀ n difieren en un factor constante, así que escribimos solo O(log n).
• Θ es simétrica: si f = Θ(g), entonces g = Θ(f). O no lo es: n = O(n²), pero n² no es O(n).
• log₂(n!) = Θ(n log n). Esa suma de logaritmos es el orden de crecimiento ajustado del logaritmo de un factorial.
• Algunos pares de funciones no son comparables. Si f(n) = n y g(n) vale 1 para n par pero n² para n impar, entonces f no es O(g) ni Ω(g).

Conteo de operaciones en bucles

Para hallar el Big O de un programa, contamos cuántas veces se ejecuta su línea principal en función de n. Unas pocas reglas resuelven casi todos los casos.

• Uno después del otro: se suma. Dos bucles en secuencia, cada uno con n pasos, cuestan n + n = 2n, que es Θ(n).
• Uno dentro del otro: se multiplica. Un bucle de n pasos que contiene otro bucle de n pasos cuesta n × n = n².
• Descarta constantes y términos menores. n² + n es Θ(n²).
• Un if / else: toma la peor rama cuando no sabes cuál se usará.

Bucles simples y bucles anidados

// ES: Un bucle que corre n veces hace n pasos: Θ(n).
for (let i = 0; i < n; i++) work();

// ES: Cada par (i, j) con i < j se visita una vez: n(n-1)/2 veces, o sea Θ(n²).
// Para n = 10 son 10 * 9 / 2 = 45 veces.
for (let i = 0; i < n; i++)
	for (let j = i + 1; j < n; j++) work();

Contar pares es como contar apretones de manos en un salón con n personas: cada par se saluda una vez, así que hay n(n-1)/2 apretones. Contar tríos i < j < k funciona igual: n(n-1)(n-2)/6 tríos. Para n = 6 son 20. Eso es Θ(n³).

Bucles que se duplican o avanzan con pasos variables

// ES: i se duplica: 1, 2, 4, 8... solo unas log2(n) iteraciones: Θ(log n).
for (let i = 1; i < n; i *= 2) work();

// ES: El externo duplica i, el interno corre i veces: 1 + 2 + 4 + ... + n es unas 2n: Θ(n).
for (let i = 1; i < n; i *= 2)
	for (let j = 0; j < i; j++) work();

// ES: El interno salta de i en i: n/1 + n/2 + n/3 + ... es unas n log n: Θ(n log n).
for (let i = 1; i <= n; i++)
	for (let j = 0; j < n; j += i) work();

El ejemplo del medio es una suma geométrica: cada término es el doble del anterior, así que la suma completa es unas dos veces el último término. El último ejemplo es una suma armónica: n/1 + n/2 + ... + n/n, que es n veces unos ln n.

El costo depende del valor, no solo del tamaño

Una prueba de primalidad simple intenta los divisores d = 2, 3, 4... mientras d × d ≤ n. En el peor caso hace unas √n divisiones, donde n es el valor que se prueba. Parece suave, pero un número de 100 dígitos tiene un valor cercano a 10¹⁰⁰, así que √n es 10⁵⁰: muchísimo más de lo posible. Medido por el número de dígitos, el costo es exponencial.

Mejor caso, peor caso y caso promedio

El mismo algoritmo puede comportarse de forma muy distinta según los datos que recibe. Buscando un nombre en una lista de n nombres: si es el primero, tuviste suerte; si es el último (o no está), tuviste mala suerte.

El peor caso es el que más se usa, porque es una promesa: 'nunca será más lento que esto'. El caso promedio necesita una suposición extra que el peor caso no necesita: una distribución de probabilidad de las entradas (por ejemplo, 'todas las posiciones son igual de probables'). Sin esa suposición, 'promedio' no significa nada.

Ordenamiento por inserción

El ordenamiento por inserción pone cada carta nueva en su lugar entre las cartas que ya tienes en la mano. En una lista ya ordenada, cada carta necesita una sola comparación: mejor caso Θ(n). En una lista invertida, cada carta pasa por todas las anteriores: peor caso Θ(n²).

Quicksort y su pivote

Quicksort elige un pivote, pone los elementos menores a un lado y los mayores al otro, y repite en cada lado. Si el pivote es siempre el primer elemento, una lista ya ordenada (o invertida) es el peor caso: el pivote es el elemento menor, un lado queda vacío y el otro tiene n - 1 elementos. El trabajo es n + (n-1) + (n-2) + ... = Θ(n²).

Con un pivote aleatorio, ninguna entrada en particular es mala. La mala suerte ahora viene de la elección aleatoria, no de los datos. El tiempo esperado es Θ(n log n) para toda entrada. Aún pueden ocurrir malos pivotes, pero son raros.

lista ordenada, pivote = primer elemento:

[1 2 3 4 5]   pivote 1 -> izq: []     der: [2 3 4 5]
[2 3 4 5]     pivote 2 -> izq: []     der: [3 4 5]
[3 4 5]       pivote 3 -> izq: []     der: [4 5]
...
n niveles, cada uno con unas n de trabajo -> Θ(n²)

Recurrencias y el teorema maestro

Algunos algoritmos resuelven un problema resolviendo copias más pequeñas del mismo problema. Esto se llama recursión. Para medirlos escribimos una ecuación que dice: 'el costo de tamaño n es el costo de las partes menores más el trabajo extra'. Esa ecuación es una recurrencia.

Escribir las recurrencias que necesitas

Para T(n) = T(n-1) + n con T(1) = 1, los valores son T(2) = 3, T(3) = 6, T(4) = 10, T(5) = 15. Es la suma 1 + 2 + ... + n = n(n+1)/2. En Hanói, para mover n discos mueves n-1 discos, mueves el disco más grande y mueves los n-1 discos otra vez, así que el trabajo se duplica con cada disco extra: T(n) = 2ⁿ - 1.

El teorema maestro

Muchas recurrencias de divide y vencerás tienen la forma T(n) = a · T(n/b) + f(n). Aquí a es el número de llamadas recursivas, n/b es el tamaño de cada llamada y f(n) es el trabajo extra fuera de las llamadas (dividir y juntar). Compara f(n) con el número n^(log_b a), que es cuánto trabajo hacen las 'hojas' de la recursión.

'Polinomialmente' significa por un factor de al menos n^ε para algún ε > 0. Ejemplos: T(n) = 2T(n/2) + n: aquí n^(log₂ 2) = n y f = n, empate, así que Θ(n log n). T(n) = 4T(n/2) + n: n^(log₂ 4) = n² le gana a n, así que Θ(n²). T(n) = T(n/2) + n: n^(log₂ 1) = 1, f = n es mayor, así que Θ(n). Strassen: T(n) = 7T(n/2) + n²: n^(log₂ 7) es unas n^2,81, que le gana a n², así que Θ(n^(log₂ 7)).

T(n) = 2T(n/2) + n

profundidad 0:   [ n ]                    -> n
profundidad 1: [n/2]   [n/2]              -> n
profundidad 2: [n/4][n/4][n/4][n/4]       -> n
...
profundidad i: 2^i nodos de tamaño n/2^i  -> n

niveles: log2(n)   total = n * log2(n)

El árbol de recursión muestra por qué. En la profundidad i hay 2^i nodos, cada uno cuesta n / 2^i, así que cada nivel suma n. Con unos log n niveles, el total es n log n.

Cuando el teorema maestro no se aplica

• T(n) = T(n-1) + n y T(n) = 2T(n-1) + 1: el subproblema es n - 1, no n dividido por algo. Usa el árbol de recursión, o expande y suma.
• T(n) = 2T(n/2) + n log n: f(n) es mayor que n, pero no polinomialmente mayor, así que cae entre los tres casos básicos. Una versión extendida da Θ(n log² n).
• T(n) = T(n/3) + T(2n/3) + n: las dos llamadas tienen tamaños distintos. El árbol de recursión tiene unos log n niveles, cada uno cuesta como mucho n, y la respuesta es Θ(n log n).

Probar por sustitución

Otro método es adivinar la respuesta y probarla por inducción. Cuidado: debes probar exactamente la afirmación que adivinaste. Si supones T(n/2) ≤ c · n/2 para T(n) = 2T(n/2) + n, obtienes T(n) ≤ cn + n. Eso no es ≤ cn, así que la prueba de T(n) = O(n) falla (y de hecho T(n) es Θ(n log n)). Concluir 'cn + n es O(n)' es un error clásico, porque la constante c debe seguir siendo la misma.

Invariantes de bucle y prueba de corrección

Ser rápido no sirve si la respuesta es incorrecta. Un invariante de bucle es una frase sobre las variables que es verdadera cada vez que el bucle empieza una vuelta nueva. Es una forma de probar que un algoritmo hace lo correcto.

Los tres pasos

// ES: Invariante: cuando corre la prueba i < n, s es la suma de a[0..i-1].
// Inicio: i = 0, s = 0 (suma vacía). Mantenimiento: sumar a[i] da la suma de a[0..i].
// Final: i = n, así que s es la suma de todo el arreglo.
let s = 0;
for (let i = 0; i < a.length; i++) s += a[i];

El ordenamiento por inserción tiene un invariante famoso: al inicio de la vuelta que inserta a[j], la parte a[0..j-1] contiene los mismos elementos del comienzo, en orden. Cuando j llega a n, todo el arreglo está ordenado.

Un buen invariante es lo bastante fuerte

Para un bucle que calcula el máximo con m = a[0], la frase 'm es igual a algún elemento del arreglo' es siempre verdadera, pero es inútil: al final no dice que m sea el mayor. El invariante correcto es 'm es el mayor de a[0..i-1]'. En la terminación, i = n y por tanto m es el mayor de todo el arreglo.

Correcto no es lo mismo que terminar

Un invariante prueba que si el bucle termina, la respuesta es correcta. También debes probar que el bucle termina. En la búsqueda binaria, si lo = mid + 1 se cambia por lo = mid, el invariante 'si x está en el arreglo, está en a[lo..hi]' sigue siendo verdadero, pero cuando hi = lo + 1 el valor de mid no cambia y el bucle corre para siempre. Para probar la terminación, muestra una cantidad que disminuye en cada vuelta y no puede bajar de un límite (aquí, hi - lo).

Análisis amortizado

Algunas operaciones son baratas casi siempre y caras de vez en cuando. Si solo miráramos la peor operación aislada, seríamos demasiado pesimistas. El análisis amortizado da el costo promedio de una operación a lo largo de una secuencia completa de operaciones en el peor caso. No interviene la probabilidad: es una garantía sobre la secuencia.

El arreglo dinámico que se duplica

Un arreglo dinámico tiene una capacidad. Agregar a un arreglo lleno es caro porque todos los elementos se copian a un arreglo nuevo con el doble de capacidad. Empezando con capacidad 1, tras 16 inserciones las copias fueron 1 + 2 + 4 + 8 = 15 en total (la inserción 17 copiaría 16 más). La suma de las copias es siempre menor que 2n, así que cada inserción cuesta O(1) amortizado.

capacidad:  1   2   4       8               16
inserción#: 1   2  3 4,5 ... 8,9 ....... 16,17
copias:     -   1   2   4              8      (crece cuando se llena)

total de copias tras 16 inserciones = 1 + 2 + 4 + 8 = 15

Si en cambio crecemos por una cantidad fija (digamos +100 posiciones), las copias son n + (n-100) + (n-200) + ... que son unas n²/200 en total. Eso es Θ(n²) para n inserciones, así que cada inserción cuesta O(n) amortizado. Duplicar (crecer por un factor) es lo que lo hace O(1).

El contador binario

Un contador binario invierte bits cuando se incrementa. El bit más bajo se invierte siempre, el siguiente cada 2 incrementos, el siguiente cada 4... Para un contador de 5 bits incrementado 16 veces, las inversiones son 16 + 8 + 4 + 2 + 1 = 31, menos de 2 por incremento. Así que un incremento cuesta O(1) amortizado, aunque un incremento pueda invertir todos los bits.

Métodos

• Método agregado: suma el costo de las n operaciones y divide entre n (lo que hicimos arriba).
• Método contable (del banquero): cobra un precio fijo por cada operación. A las operaciones baratas se les cobra más de lo que cuestan, y el extra va a un banco como crédito. Las operaciones caras se pagan con el crédito. El banco nunca puede quedar en negativo.
• Método del potencial: una versión más formal de la misma idea, con una 'energía potencial' guardada en la estructura de datos.

La cota inferior del ordenamiento por comparación

Hasta ahora buscamos algoritmos más rápidos. Ahora preguntamos: ¿existe un límite de velocidad que ningún algoritmo de ordenamiento puede superar? Para los algoritmos que ordenan comparando dos elementos a la vez (como merge sort, quicksort y heap sort), la respuesta es sí: Ω(n log n).

El árbol de decisión

Dibuja cada comparación que hace el algoritmo como una rama: '¿a < b?' va a la izquierda si es sí y a la derecha si es no. Cada camino de la raíz a una hoja es una ejecución del algoritmo, y la hoja dice qué orden se encontró. Para n elementos distintos hay n! órdenes posibles, y cada uno debe aparecer como hoja. Por tanto el árbol tiene al menos n! hojas.

ordenando 3 elementos a, b, c  (3! = 6 órdenes = 6 hojas)

            a < b ?
          /         \
     b < c ?       a < c ?
     /     \       /     \
  abc    a<c?    bac    b<c?
         /  \           /  \
       acb  cab       bca  cba

Un árbol binario de altura h tiene como máximo 2^h hojas. Entonces 2^h ≥ n!, y la altura cumple h ≥ log₂(n!). La altura es el número de comparaciones en el peor caso. Y log₂(n!) = Θ(n log n). Por lo tanto, cualquier ordenamiento por comparación necesita Ω(n log n) comparaciones en el peor caso.

Para 4 elementos: 4! = 24 órdenes, y 2⁴ = 16 < 24 ≤ 32 = 2⁵, así que se necesitan al menos 5 comparaciones. Para 5 elementos: 5! = 120 > 2⁶ = 64, así que nadie puede ordenar 5 elementos con 6 comparaciones en el peor caso: esa afirmación no puede ser verdadera.

¿Cómo pueden algunos ordenamientos ser más rápidos?

La cota solo vale para los ordenamientos que averiguan los datos comparando. Los que usan los propios valores se escapan de ella:

No contradicen la cota porque nunca preguntan '¿a < b?'. Usan el valor como índice en una tabla. El precio: el rango k debe ser pequeño, y solo funcionan con cosas como enteros o claves cortas.

Complejidad espacial

El tiempo no es lo único que cuesta. Un algoritmo también usa memoria. La complejidad espacial mide la memoria que necesita un algoritmo cuando la entrada crece. Normalmente contamos el espacio auxiliar: la memoria extra usada además de la propia entrada.

Espacio auxiliar O(1) significa un número fijo de variables extra, que no crece con n. Cuidado: 'en el mismo lugar' con recursión igual usa espacio, porque cada llamada que no terminó queda guardada en la pila de llamadas. Si una función se llama a sí misma n veces en cadena, la pila guarda n llamadas: O(n).

// ES: Cada llamada espera a la siguiente, así que se apilan n marcos: espacio O(n).
// (Sin optimización de llamada en cola, que la mayoría de los lenguajes no garantiza.)
function sum(n: number): number {
	if (n === 0) return 0;
	return n + sum(n - 1);
}

Quicksort particiona en el mismo lugar, pero recursa en ambos lados. Si el pivote es siempre el peor, la cadena de llamadas tiene profundidad n, así que la pila es O(n). Fibonacci con dos llamadas hace un número exponencial de llamadas en total, pero en un solo momento solo hay un camino abierto desde la raíz, con como máximo n llamadas de profundidad, así que la pila es O(n).

También hay un vínculo con el tiempo. Si cada paso toca un número constante de celdas de memoria, un algoritmo no puede usar más celdas que pasos tiene. Entonces S(n) = O(T(n)): el espacio nunca es mayor que el tiempo. Lo contrario es falso: un algoritmo puede tardar mucho usando casi nada de memoria.

Complejidad de las operaciones comunes de estructuras de datos

Elegir una estructura de datos es elegir qué operaciones son baratas. Aquí están los costos que debes conocer, con n elementos.

Veamos por qué se cumplen algunas de ellas.

Arreglos y listas enlazadas

Un arreglo guarda los elementos uno junto al otro, así que la posición i se encuentra con una cuenta simple: O(1). Pero insertar al comienzo empuja cada elemento un lugar a la derecha: O(n). Una lista enlazada es una cadena de cajitas, cada una apuntando a la siguiente, así que insertar al comienzo solo cambia un puntero: O(1). Para llegar a la i-ésima cajita hay que recorrer la cadena: O(n).

Tablas hash

Una tabla hash con una buena función hash y un factor de carga controlado (elementos por cajón) encuentra una clave en O(1) en promedio. Con encadenamiento (cada cajón guarda una lista), si todas las claves caen en el mismo cajón, la búsqueda recorre una lista de n claves: O(n) en el peor caso.

Árboles y heaps

Un árbol binario de búsqueda guarda las claves menores a la izquierda y las mayores a la derecha. Si insertas 1, 2, 3, ..., n en orden en un árbol simple sin balanceo, cada clave va a la derecha y el árbol se vuelve una lista: buscar n cuesta O(n). Un árbol balanceado (AVL, rojinegro) se repara solo y mantiene la altura en O(log n), así que da búsqueda, inserción y eliminación en O(log n) en el peor caso, y un recorrido en orden lista las claves ordenadas en O(n). Una tabla hash no lista las claves en orden, así que solo el árbol balanceado cumple todos estos requisitos.

Un min-heap binario guarda el elemento menor en la raíz: leerlo es O(1), eliminarlo es O(log n) (se mueve el último elemento a la raíz y se deja hundir). Construir un heap a partir de un arreglo cualquiera con sift-down desde el último nodo interno hasta la raíz cuesta solo O(n), no O(n log n), porque la mayoría de los nodos están cerca del fondo y se hunden muy poco.

Una cola sobre un arreglo

Si una cola es un arreglo, encolar escribe al final (O(1) amortizado), pero desencolar elimina el índice 0 y desplaza todos los demás: O(n). Para n encolados y n desencolados el total es O(n²). Una lista enlazada, o un arreglo con dos índices que avanzan (un buffer circular), lleva cada operación a O(1).

P, NP e intratabilidad

Hasta aquí todos los algoritmos que vimos son 'suficientemente rápidos'. Pero algunos problemas parecen no tener ningún algoritmo rápido. Para hablar de ellos, los científicos de la computación clasifican los problemas en clases.

Polinomial y no polinomial

Un algoritmo corre en tiempo polinomial si su costo está acotado por n elevado a una potencia fija: n, n log n, n², n³⁰⁰... Algoritmos como 2ⁿ o n! no son polinomiales (son exponenciales o peores). Incluso n^(log n) no es polinomial. Los algoritmos polinomiales se llaman tratables (manejables). Los demás son intratables para entradas grandes: ni un computador un millón de veces más rápido salva al 2ⁿ.

Las clases

     +--------------------------+
     |           NP             |
     |    +----------+          |
     |    |    P     |   NP-    |
     |    |          | completo |
     |    +----------+          |
     +--------------------------+

  P está dentro de NP.  ¿P = NP?  Nadie lo sabe.

Datos que necesitas

• P ⊆ NP: si puedes resolver un problema rápido, también puedes verificar una respuesta rápido.
• P = NP es una pregunta abierta. Nadie lo ha probado, y nadie ha probado lo contrario. La mayoría de los expertos cree que P ≠ NP, pero eso es una creencia, no un teorema.
• Un problema de decisión tiene respuesta sí/no. La versión de decisión del problema del viajante pregunta: '¿existe un recorrido que visite las n ciudades una vez y vuelva al inicio con costo como máximo K?'. Está en NP porque, dado un recorrido, verificas en tiempo polinomial que visita cada ciudad una vez y que el costo es como máximo K.
• Si alguien encuentra un algoritmo polinomial para un problema NP-completo (como SAT, la satisfacibilidad de fórmulas lógicas), entonces todo problema de NP tiene uno, y P = NP.
• Para probar que un problema nuevo X es NP-difícil, toma un problema A ya conocido como NP-completo y construye una reducción en tiempo polinomial de A a X: una forma rápida de convertir cualquier instancia de A en una instancia de X con la misma respuesta. Si X fuera fácil, A sería fácil.

Fíjate en el sentido de la reducción: reduces el problema difícil conocido al nuevo. Hacerlo al revés (del nuevo al conocido) solo mostraría que el problema nuevo no es más difícil que A, lo cual no prueba nada sobre su dificultad.

Juntando todo

Todas las herramientas de esta área responden a una pregunta: ¿cómo crece el costo de un algoritmo con el tamaño de la entrada? Mira cómo se conectan las piezas.

Errores comunes

• Pensar que Big O da el tiempo en segundos. Da la forma del crecimiento.
• Confundir el mejor, peor y caso promedio con las notaciones O, Ω y Θ.
• Decir Θ cuando solo probaste O.
• Olvidar descartar constantes y términos menores, o descartar un término que importa (por ejemplo dentro de un exponente).
• Ignorar la memoria que usa la recursión.
• Usar el teorema maestro cuando la recurrencia no tiene la forma a · T(n/b) + f(n).
• Creer que un computador más rápido cambia el orden de crecimiento.
• Leer NP como 'no polinomial'.