Ya sabemos qué es un algoritmo y qué tipos existen; ahora necesitamos un lenguaje riguroso para responder a la pregunta clave del curso: ¿cuál de estos dos algoritmos es más eficiente?. Ese lenguaje es la notación asintótica: una forma de describir cómo crece el coste de un algoritmo a medida que crece el tamaño de su entrada, sin depender del ordenador, del lenguaje ni del cronómetro. Dominarla es imprescindible: la usaremos en cada lección restante del curso, aparece en toda la documentación técnica seria (¿has visto "O(1) average" en la documentación de los diccionarios de Python?) y es pregunta fija en entrevistas técnicas.

1. Por qué medir el crecimiento y no el tiempo de reloj
2. La idea central: cómo escala el coste con n
3. O grande, Ω y Θ: qué significa cada una
4. Jerarquía de órdenes comunes con la red de RutaBus
5. Reglas prácticas de simplificación
6. Qué viene después: el Módulo 2

La primera tentación al comparar algoritmos es cronometrarlos. Hagamos el experimento mental con RutaBus: dos desarrolladores implementan la búsqueda de una parada por nombre y miden el tiempo con 10.000 paradas.

¿Es mejor el algoritmo de A? No podemos saberlo con estos datos. El tiempo de reloj mezcla demasiadas cosas ajenas al algoritmo:

• El hardware: CPU, memoria caché, disco... La misma búsqueda lineal puede ser 50 veces más rápida en una máquina que en otra.
• El lenguaje y su implementación: Python interpretado vs C compilado; incluso versiones distintas de Python.
• El estado del sistema: otros procesos, el sistema operativo, la suerte.
• El tamaño de entrada elegido: con 10 paradas casi cualquier algoritmo parece instantáneo; las diferencias explotan al crecer los datos.

Lo que sí es una propiedad del algoritmo (y no de la máquina) es cuántas operaciones básicas necesita en función del tamaño de la entrada, n. Si repetimos el experimento variando n (el número de paradas), el panorama cambia:

La máquina rápida de A le da ventaja con n pequeño, pero ninguna máquina compensa una diferencia de crecimiento: al millón de paradas, el algoritmo de B hace 50.000 veces menos trabajo. La notación asintótica captura exactamente esto: el ritmo de crecimiento del coste cuando n se hace grande, ignorando factores constantes que dependen de la máquina.

Llamamos n al tamaño de la entrada (número de paradas de la red, número de horarios a ordenar...) y f(n) al número de operaciones básicas que realiza el algoritmo para esa entrada. La pregunta asintótica es: cuando n se duplica, ¿qué le pasa a f(n)?

• Si f(n) = 3n + 5, al duplicar n el coste aproximadamente se duplica: crecimiento lineal.
• Si f(n) = n², al duplicar n el coste se multiplica por 4: crecimiento cuadrático.
• Si f(n) = 20 (no depende de n), el coste no cambia: crecimiento constante.

Fíjate en que el "3" y el "+5" de la primera función apenas importan para esta pregunta: 3n + 5 y 900n + 2000 se comportan igual cualitativamente (duplicar n ≈ duplicar coste), aunque una sea 300 veces más lenta que la otra. Ese factor 300 es el que absorbe la máquina, el lenguaje, etc.; el tipo de crecimiento, no. Por eso la notación asintótica descarta constantes y se queda con la forma de la curva.

Las tres notaciones expresan cotas sobre el crecimiento de f(n). Definición semi-formal y, sobre todo, su significado práctico:

Decimos que f(n) es O(g(n)) si, a partir de cierto tamaño de entrada, f(n) queda por debajo de g(n) multiplicada por alguna constante. Formalmente: existen constantes c > 0 y n₀ tales que f(n) ≤ c·g(n) para todo n ≥ n₀.

Traducción práctica: "el coste del algoritmo no crece más rápido que g(n)". Es una garantía hacia arriba: por eso es la notación más usada, ya que a los ingenieros nos interesa acotar el peor comportamiento posible.

Ejemplo: la búsqueda lineal de una parada hace como mucho n comparaciones → es O(n). Nota técnica: también sería formalmente correcto decir que es O(n²) (una cota superior más holgada), pero por convención se da siempre la cota más ajustada conocida.

Decimos que f(n) es Ω(g(n)) si, a partir de cierto n, f(n) queda por encima de c·g(n) para alguna constante c > 0.

Traducción práctica: "el coste no puede ser menor que ese orden". Sirve para expresar límites de lo posible. Ejemplo: cualquier algoritmo que deba mostrar todas las paradas de la red es Ω(n) — no hay forma de listar n cosas sin al menos n pasos.

Decimos que f(n) es Θ(g(n)) si es a la vez O(g(n)) y Ω(g(n)): el coste queda atrapado entre dos múltiplos de g(n).

Traducción práctica: "el coste crece exactamente al ritmo de g(n)". Es la caracterización más informativa cuando se puede dar. Ejemplo: contar las paradas de una lista recorriéndola entera es Θ(n): ni más ni menos que un paso por parada.

Un matiz que conviene dejar apuntado: estas notaciones describen el crecimiento de una función de coste, y un mismo algoritmo puede tener funciones de coste distintas según la entrada le sea favorable o no (la búsqueda lineal encuentra "Plaza Mayor" a la primera si está al principio de la lista...). Ese análisis por mejor, peor y caso promedio tiene su propia lección (02-03); de momento, cuando digamos que un algoritmo "es O(n)" nos referiremos a su comportamiento en el peor de los casos, que es el uso más habitual de la O grande.

Estos son los órdenes de crecimiento que te encontrarás una y otra vez, de mejor a peor:

Los nombres cobran vida con números concretos. Supongamos que cada operación cuesta 1 microsegundo (una millonésima de segundo) y usemos como n el número de paradas de la red de RutaBus:

Lecturas importantes de esta tabla:

• O(log n) es casi tan bueno como O(1): pasar de 10 a 100.000 paradas solo multiplica el coste por ~6. Duplicar n añade una operación. Por eso la búsqueda binaria es tan valiosa.
• O(n log n) escala muy bien: ordenar 100.000 horarios cuesta menos de 2 segundos. Es el orden de los buenos algoritmos de ordenación.
• O(n²) se vuelve inviable sorprendentemente pronto: con la red de una gran ciudad (100.000 paradas), calcular todas las distancias entre pares llevaría horas. Un algoritmo cuadrático que "iba bien en pruebas" con 100 paradas puede hundir la aplicación en producción.
• O(2ⁿ) es intratable salvo para n minúsculo: con solo 100 elementos, el universo no ha existido suficiente tiempo para terminar el cálculo. Cuando un problema solo admite soluciones exponenciales exactas, entran en juego las heurísticas que vimos en la lección anterior.

Como referencia rápida en Python (el porqué exacto de cada coste se analiza en el Módulo 2):

Cuando exprese el coste de un algoritmo, la notación asintótica se simplifica con dos reglas mecánicas:

Los factores constantes dependen de la máquina y el lenguaje, no del algoritmo, así que se eliminan:

• 5n → O(n)
• n/2 → O(n) (dividir por 2 es multiplicar por la constante 0,5)
• 300 → O(1) (cualquier coste fijo, por grande que sea, es constante)

Cuidado: esto no significa que las constantes no importen en la vida real. Entre dos algoritmos O(n), el de constante pequeña gana; la notación solo dice que ese matiz no cambia la forma del crecimiento. Retomaremos esta tensión en el Módulo 5 (optimización).

Cuando el coste es una suma de términos, para n grande uno de ellos "engulle" a los demás — el que crece más rápido según la jerarquía que acabamos de ver:

• n² + 10n + 500 → O(n²)
• n log n + n → O(n log n)
• 2ⁿ + n³ → O(2ⁿ)

¿Por qué es legítimo? Compruébalo con números: para n = 10.000, n² = 100.000.000 mientras que 10n + 500 = 100.500 — menos del 0,1% del total. Cuanto mayor es n, más irrelevante es el término menor.

Una función de RutaBus hace lo siguiente con una red de n paradas:

1. Lee la configuración de la app → coste fijo: 25 operaciones.
2. Ordena las paradas alfabéticamente → n log n operaciones.
3. Recorre la lista ordenada para marcar las accesibles → n operaciones.
4. Comprueba las 2 paradas favoritas del usuario → 2 operaciones.

Coste total: f(n) = n log n + n + 27. Aplicando las reglas: descartamos las constantes (27) y nos quedamos con el término dominante (n log n engulle a n). Resultado: O(n log n).

Tabla de práctica rápida:

Con la notación asintótica ya sabemos expresar la eficiencia de un algoritmo. Lo que todavía no hemos hecho es derivarla a partir del código: mirar una función Python línea a línea, contar sus operaciones y bucles, y concluir "esto es O(n²)". Ese es exactamente el objetivo de la próxima lección (02-01, complejidad temporal). Después el Módulo 2 completa el cuadro con la complejidad espacial (cuánta memoria consume un algoritmo, 02-02) y el análisis por casos mejor, peor y promedio (02-03), que aquí solo hemos dejado apuntado.

• Comparar algoritmos cronometrándolos en una sola máquina y con un solo tamaño de entrada. El benchmark tiene su lugar (Módulo 5), pero la conclusión "A es mejor que B" solo es sólida si comparas crecimientos. Consejo: si mides, mide con varios n crecientes (n, 2n, 4n...) y observa cómo escala cada uno.
• Creer que O grande describe el tiempo exacto. O(n) no dice "tarda n segundos" ni "hace exactamente n operaciones"; dice que el coste crece como mucho linealmente. Dos algoritmos O(n) pueden diferir en un factor 100.
• Ignorar las constantes cuando n es pequeño. Para n = 20, un O(n²) simple puede ganar a un O(n log n) sofisticado. La asintótica manda cuando n crece; con datos minúsculos, mide.
• Usar O, Ω y Θ como sinónimos. Decir "este algoritmo es Ω(n²)" afirma que al menos cuesta n² — probablemente querías decir O(n²) (como mucho) o Θ(n²) (exactamente). Revisa qué cota quieres expresar.
• Sumar en lugar de quedarse con el dominante... o al revés. Pasos secuenciales se suman y luego domina el mayor: O(n) seguido de O(n log n) es O(n log n), no O(n · n log n). La multiplicación aparece con bucles anidados, que analizaremos en 02-01.
• Pensar que "asintótico" es teoría irrelevante. Las tablas de crecimiento muestran lo contrario: la diferencia entre O(n²) y O(n log n) es la diferencia entre una app que responde al instante y una que se cuelga cuando la ciudad añade paradas.

Simplifica a su orden asintótico (O grande) cada una de estas funciones de coste, indicando qué regla aplicas:

a) f(n) = 4n + 90 b) f(n) = n²/10 + 50n + 3 c) f(n) = 1000 d) f(n) = 2n log n + n² + 7n e) f(n) = log n + 25

La red de RutaBus va a crecer de 1.000 a 100.000 paradas (multiplicarse por 100). Para cada uno de estos tres algoritmos, calcula (aproximadamente) por cuánto se multiplicará su número de operaciones, y decide cuáles seguirán siendo viables si hoy tardan 1 ms con 1.000 paradas:

a) Algoritmo X: O(n) b) Algoritmo Y: O(n²) c) Algoritmo Z: O(log n) — usa log₂(1.000) ≈ 10 y log₂(100.000) ≈ 17

Indica si cada afirmación es verdadera o falsa y justifícalo:

a) Un algoritmo O(n²) siempre tarda más que uno O(n), para cualquier entrada. b) Si un algoritmo es Θ(n), entonces también es O(n) y Ω(n). c) Mostrar por pantalla las n paradas de la red puede hacerse en O(log n). d) f(n) = 5n + 20 es O(n²).

Solución 1:

a) O(n) — regla 1: se descartan la constante multiplicativa 4 y la aditiva 90. b) O(n²) — regla 2: n² domina a 50n; regla 1: se descartan el 1/10 y el 3. c) O(1) — un coste fijo, por grande que sea, es constante. d) O(n²) — regla 2: en la jerarquía, n² crece más rápido que n log n, así que domina. e) O(log n) — la constante 25 se descarta; queda el término logarítmico.

Solución 2:

a) X (O(n)): el coste escala linealmente → ×100. De 1 ms pasaría a ~100 ms. Viable, aunque empieza a notarse. b) Y (O(n²)): el coste escala con el cuadrado → ×100² = ×10.000. De 1 ms pasaría a ~10 segundos. Inviable para una operación interactiva de la app. c) Z (O(log n)): el coste pasa de ~10 a ~17 unidades → ×1,7. De 1 ms pasaría a ~1,7 ms. Perfectamente viable: esta es la magia del crecimiento logarítmico.

Solución 3:

a) Falsa. La notación describe el crecimiento para n grande, no el tiempo para toda entrada: con n pequeño, las constantes pueden hacer que el O(n²) gane (p. ej., 2n² frente a 1000n para n < 500). Lo que sí es cierto: a partir de algún n, el O(n) siempre acaba ganando. b) Verdadera. Es la definición de Θ: cota ajustada significa ser a la vez cota superior (O) e inferior (Ω) del mismo orden. c) Falsa. Producir n líneas de salida exige al menos n operaciones: el problema es Ω(n), y ninguna astucia algorítmica puede bajar de ahí. d) Verdadera, pero engañosa. Formalmente 5n + 20 ≤ n² a partir de cierto n, así que la afirmación cumple la definición de O. Sin embargo, la cota ajustada es O(n) — y por convención siempre se da la más ajustada conocida. Este matiz (que O es solo una cota superior) es la fuente del error de usarla como si fuera Θ.

En esta lección hemos adquirido el lenguaje con el que se habla de eficiencia en informática. Hemos visto por qué el tiempo de reloj no sirve para comparar algoritmos (mide la máquina tanto como el método) y por qué sí sirve el ritmo de crecimiento del coste respecto al tamaño de la entrada. Hemos definido las tres notaciones —O grande como cota superior, Ω como cota inferior y Θ como cota ajustada—, hemos recorrido la jerarquía de órdenes comunes desde O(1) hasta O(2ⁿ) comprobando con la red de paradas de RutaBus que la diferencia entre ellos no es académica sino brutal, y hemos practicado las dos reglas de simplificación: descartar constantes y quedarse con el término dominante. Con este lenguaje en la mano, en el Módulo 2 aprenderemos a calcular la complejidad de un algoritmo real: analizaremos código Python línea a línea para derivar su complejidad temporal (02-01), mediremos también su consumo de memoria (02-02) y distinguiremos su comportamiento en el mejor caso, el peor y el promedio (02-03) — empezando, cómo no, por los algoritmos que ya hemos escrito para RutaBus.