En el Módulo 1 aprendimos el lenguaje de la eficiencia: la notación asintótica. Ahora vamos a aprender a usarlo: dado un fragmento de código Python real, ¿cómo se calcula su complejidad temporal? En esta lección desarrollaremos el método de análisis línea a línea: asignar un coste a cada operación, sumar los costes de las líneas secuenciales, multiplicar por las repeticiones de los bucles y simplificar con las reglas que ya conocemos. Lo aplicaremos paso a paso a las funciones que ya escribimos para RutaBus, incluyendo una función recursiva, y terminaremos con algo que sorprende a muchos desarrolladores: operaciones de Python que parecen de un solo paso pero esconden un bucle dentro.

Dos avisos antes de empezar. Primero: las definiciones de O, Ω y Θ las dimos en la lección 01-03 y aquí las damos por sabidas (recuerda: O grande es una cota superior del crecimiento del coste). Segundo: en toda esta lección analizamos el peor caso — el escenario de entrada que más trabajo provoca —, porque es el análisis más habitual y el más prudente. En la lección 02-03 veremos que también existen el mejor caso y el caso promedio, y cuándo interesa cada uno.

1. El modelo de coste: operaciones elementales
2. Código secuencial: sumar costes
3. Bucles simples: multiplicar por las repeticiones
4. Análisis completo de parada_mas_cercana
5. Bucles anidados: pares de paradas conectables
6. Bucles dependientes: la suma aritmética
7. Llamadas a funciones: el coste no desaparece
8. Funciones recursivas: contar las llamadas
9. Costes ocultos de las operaciones de Python

Para analizar código sin cronometrarlo necesitamos un acuerdo: ¿qué cuenta como "un paso"? La convención es esta:

• Una operación elemental es cualquier operación cuyo tiempo no depende del tamaño de la entrada: una asignación (x = 5), una operación aritmética (a + b, a * b), una comparación (a < b), un acceso a una posición de lista (lista[i]), un return.
• Cada operación elemental cuesta O(1): tiempo constante. No nos importa si en una máquina concreta una multiplicación tarda el doble que una suma — la lección 01-03 ya nos enseñó que las constantes se descartan.

Con este modelo, analizar un algoritmo se reduce a contar cuántas operaciones elementales se ejecutan en función de n (el tamaño de la entrada). El resultado es una función de coste T(n) que después simplificamos a su orden asintótico.

Ojo: la palabra clave es elemental. Como veremos en el último apartado, en Python hay expresiones de una sola línea que no son elementales porque esconden un recorrido completo. De momento, asumamos que trabajamos con las operaciones de la lista anterior.

La primera regla del análisis línea a línea:

Regla 1 (secuencia): el coste de varias instrucciones ejecutadas una tras otra es la suma de sus costes.

Coste total: O(1) + O(1) + O(1) + O(1) = O(1). Da igual que sean 4 líneas o 400: si ninguna depende de n, la suma sigue siendo una constante y por tanto O(1). Esta es la traducción práctica de "descartar constantes" que vimos en 01-03: un bloque secuencial de operaciones elementales, por largo que sea, cuesta tiempo constante.

Regla 2 (bucle): el coste de un bucle es el coste de su cuerpo multiplicado por el número de iteraciones.

Recuperemos contar_paradas_iterativo de la lección 01-02:

Contemos con n = número de paradas:

T(n) = O(1) + O(n) + O(1). Aplicando la regla del término dominante de 01-03: T(n) = O(n). Lineal: si la red de RutaBus duplica sus paradas, contar tarda el doble.

Un matiz importante: el número de iteraciones no siempre es exactamente n. Un bucle for parada in paradas[1:] itera n−1 veces; uno que recorre la mitad de la lista itera n/2 veces. Asintóticamente n−1, n/2 y n son todos O(n) — las constantes multiplicativas y aditivas se descartan. Lo que importa es que el número de vueltas crece linealmente con n.

Apliquemos el método completo a la primera función que escribimos para RutaBus (lección 01-01). Anotamos el coste de cada línea como comentario:

Procedimiento:

1. Antes del bucle: dos líneas O(1) → O(1) en total.
2. Cuerpo del bucle: cuatro operaciones O(1) → O(1) por iteración. (Las dos últimas solo se ejecutan si la comparación es cierta, pero como analizamos el peor caso asumimos que se ejecutan siempre; y aunque no lo hicieran, 2 operaciones frente a 4 es una constante que se descarta.)
3. El bucle: O(1) por iteración × (n−1) iteraciones = O(n).
4. Después del bucle: O(1).

T(n) = O(1) + O(n) + O(1) = O(n). Confirmamos formalmente lo que en 01-01 solo intuíamos: encontrar la parada más cercana con un recorrido lineal cuesta tiempo lineal. Para la red completa de una ciudad (miles de paradas) sigue siendo perfectamente asumible.

Regla 3 (anidamiento): cuando un bucle contiene otro bucle, los costes se multiplican: iteraciones del externo × iteraciones del interno × coste del cuerpo.

Nueva necesidad de RutaBus: el equipo de planificación quiere saber qué pares de paradas están lo bastante cerca como para conectarlas con un tramo directo de línea (digamos, a menos de 2 km). La solución natural: comparar cada parada con cada una de las demás.

Análisis:

• El cuerpo más interno es O(1).
• El bucle interno lo ejecuta n veces → O(n) por cada vuelta del externo.
• El bucle externo da n vueltas → n × O(n) = O(n²).

La comparación p1["nombre"] < p2["nombre"] es un truco para procesar cada par una sola vez (evita examinar tanto ("A","B") como ("B","A") y los pares de una parada consigo misma), pero no cambia el orden: el if se evalúa en las n² combinaciones aunque solo prospere en la mitad, y n²/2 sigue siendo O(n²).

¿Es grave un O(n²)? Depende de n, y aquí conecta con la tabla de tiempos de 01-03: con 100 paradas son 10.000 comparaciones (instantáneo); con 10.000 paradas de un área metropolitana son 100 millones (segundos). Los algoritmos cuadráticos son la primera señal de alarma que un desarrollador aprende a detectar: un bucle dentro de otro bucle, ambos sobre la misma colección.

En pares_conectables hay un desperdicio evidente: cuando p1 es la parada 7, no hace falta compararla con las paradas 0 a 7 (ya se compararon antes o es ella misma). La versión afinada hace que el bucle interno dependa del externo:

Ahora el bucle interno no da siempre n vueltas: da n−1 cuando i=0, n−2 cuando i=1... y 0 cuando i=n−1. Ya no podemos multiplicar sin más; hay que sumar las iteraciones reales:

Esta es la famosa suma aritmética, y su valor exacto es:

Un truco visual para recordarla: escribe la suma dos veces, una al derecho y otra al revés, y empareja términos:

El doble de la suma es n(n−1), luego la suma es n(n−1)/2. Aplicando las reglas de simplificación de 01-03 (descartar constantes como el ½, quedarse con el término dominante n²): O(n²).

Conclusión que conviene interiorizar: la versión v2 hace la mitad de trabajo real que la v1 — mejora útil en la práctica —, pero su orden de crecimiento es el mismo, O(n²). La notación asintótica es deliberadamente ciega a los factores constantes; para pasar de O(n²) a algo mejor no basta con recortar iteraciones, hay que cambiar de estrategia (de eso trata el Módulo 3). Este patrón "bucle interno que empieza donde va el externo → n(n−1)/2 → O(n²)" aparece constantemente: memorízalo.

Regla 4 (llamadas): el coste de una llamada a función es el coste de ejecutar su cuerpo con los argumentos dados. Encapsular código en una función no lo hace gratis.

En parada_mas_cercana dijimos alegremente que distancia(...) era O(1). Eso hay que justificarlo mirando su cuerpo:

Restas, cuadrados, una raíz: número fijo de operaciones elementales, independiente de cuántas paradas tenga la red → O(1). Correcto.

Pero cuidado con este otro caso, muy típico:

Una sola línea, dos llamadas... y cada llamada a hay_parada_iterativa (lección 01-02) es un recorrido lineal: O(n). Total: O(n) + O(n) = O(n), no O(1). Y si esa función se llama dentro de un bucle sobre las n paradas, el conjunto pasa a ser O(n²). La regla práctica: al ver una llamada, pregúntate siempre cuánto cuesta por dentro — o búscalo en su documentación. Este será exactamente el problema de los "costes ocultos" del último apartado.

Para una función recursiva no hay bucle que multiplicar, pero la idea es la misma con otro disfraz:

Coste de una recursión = (número de llamadas) × (coste de cada llamada, sin contar la llamada recursiva)

Analicemos contar_paradas_recursivo de la lección 01-02:

Paso 1 — contar las llamadas. Cada llamada trabaja con una lista una unidad más corta que la anterior. Para una línea con 4 paradas:

Para n paradas: n + 1 llamadas. El número de llamadas crece linealmente con n.

Paso 2 — coste de cada llamada. Aquí viene la sorpresa. La comparación y el + 1 son O(1), pero paradas[1:] crea una lista nueva copiando todos los elementos menos el primero: si la lista tiene k elementos, el slice cuesta O(k) (lo confirmaremos en la tabla del apartado siguiente). Así que las llamadas cuestan, respectivamente, n, n−1, n−2, ..., 1, 0 operaciones de copia. ¿Te suena esa suma? Es otra vez la suma aritmética: n(n+1)/2 → O(n²).

Resultado honesto: tal y como está escrita en Python, contar_paradas_recursivo es O(n²), mientras que su hermana iterativa es O(n). Si la reescribiéramos pasando un índice en lugar de trocear la lista (evitando el slice), cada llamada sería O(1) y la recursión completa quedaría en O(n), como dicta la intuición de "n+1 llamadas de coste constante". Moraleja doble: (1) la técnica para recursiones es contar llamadas y multiplicar por el coste de cada una; (2) en Python, ese coste "de cada una" puede esconder copias.

Para recursiones más ricas — por ejemplo una función que se llama dos veces a sí misma con la mitad del problema, como hará merge sort — este conteo artesanal se formaliza con las llamadas ecuaciones de recurrencia. No las necesitamos todavía: las plantearemos y resolveremos para un caso real en la lección 04-03 (Merge Sort). Quédate con la versión intuitiva: dibuja el árbol de llamadas, cuenta cuántas hay y cuánto cuesta cada una.

Python es un lenguaje de muy alto nivel: una sola expresión puede ejecutar un bucle completo en C por debajo. Para el análisis de complejidad eso es una trampa: el código se lee como una línea pero cuesta como un bucle. Esta tabla recoge los casos que más análisis arruinan (n = tamaño de la colección implicada; todos en el peor caso):

Veamos dos de estas trampas en código de RutaBus.

Trampa 1: in sobre lista dentro de un bucle. Queremos las paradas comunes a dos líneas (posibles transbordos):

Parece un bucle simple → O(n), pero el in sobre una lista es un recorrido lineal escondido: n iteraciones × O(n) por comprobación = O(n²). Es exactamente el mismo anidamiento de pares_conectables, solo que uno de los dos bucles no se ve. Arreglo idiomático: convertir linea_b en un set (paradas_b = set(linea_b), coste O(n) una sola vez) y preguntar parada in paradas_b, que es O(1) — el algoritmo completo baja a O(n). El precio es memoria extra, y medir ese precio es justo el tema de la próxima lección.

Trampa 2: concatenación de strings en bucle. Generar el rótulo con el recorrido de una línea:

En la vuelta k, rotulo ya mide proporcionalmente k caracteres y la concatenación lo copia entero: costes 1, 2, 3, ..., n → suma aritmética → O(n²). La versión idiomática, " - ".join(paradas), construye el resultado en un solo paso de coste O(total de caracteres): lineal.

• Sumar donde hay que multiplicar (y viceversa): instrucciones en secuencia se suman; instrucciones dentro de un bucle se multiplican por las iteraciones. Dos bucles seguidos sobre n elementos son O(n) + O(n) = O(n); un bucle dentro de otro es O(n · n) = O(n²).
• Creer que menos líneas = menos coste: if parada in linea_b es una línea y cuesta O(n). El coste se mide en operaciones ejecutadas, no en líneas escritas. Ante cualquier función o método de biblioteca, consulta su coste (la tabla anterior cubre lo esencial).
• Concluir O(n²/2) o O(3n): son órdenes mal escritos. Tras contar, simplifica siempre con las dos reglas de 01-03: fuera constantes, fuera términos no dominantes. O(n²/2) es O(n²); O(3n) es O(n).
• Olvidar de qué es n: en transbordos hay dos entradas (dos líneas). Si tienen tamaños distintos, lo riguroso es decir O(a · b). Decimos O(n²) asumiendo tamaños parecidos, pero conviene ser explícito cuando no lo son.
• Ignorar el coste de los slices en recursiones: f(lista[1:]) parece elegante pero copia la lista en cada nivel. Si la recursión tiene profundidad n, esas copias suman O(n²). Alternativa: pasar índices (f(lista, i+1)).
• Consejo: entrena el ojo con este atajo mental — ¿cuántas veces se ejecuta la línea más interna del código? Esa cuenta, simplificada, es casi siempre la complejidad del algoritmo.

Ejercicio 1. Analiza línea a línea la siguiente función de RutaBus y da su complejidad temporal en el peor caso. Indica cuántas veces se ejecuta cada línea.

Ejercicio 2. El equipo de calidad de RutaBus escribió esta función para detectar paradas duplicadas en el fichero maestro de la red. Analiza su complejidad y propón una versión O(n) usando la tabla de costes de Python. Justifica el coste de ambas.

Ejercicio 3. Sin ejecutarla, determina la complejidad de esta función recursiva que invierte el orden de las paradas de una línea (útil para mostrar el trayecto de vuelta). Pista: cuenta las llamadas y fíjate en el coste de cada llamada.

Solución 1. Las dos asignaciones iniciales y el return son O(1) (se ejecutan 1 vez). Cada bucle ejecuta su cuerpo n veces con coste O(1) por iteración → O(n) cada uno. Son bucles en secuencia, no anidados, así que se suman: T(n) = O(1) + O(n) + O(n) + O(1) = O(2n) → O(n). Error común aquí: ver dos for y responder O(n²) — solo se multiplica cuando uno está dentro del otro.

Solución 2. Es el patrón de bucle dependiente: el bucle interno da n−1, n−2, ..., 1, 0 vueltas → suma aritmética n(n−1)/2 → O(n²) en el peor caso (sin duplicados: hay que comprobar todos los pares; nota que si encuentra un duplicado pronto termina antes — esa diferencia entre escenarios es justo el tema de 02-03). Versión lineal con un conjunto:

n iteraciones × O(1) = O(n). El precio: hasta O(n) de memoria extra para vistas — lo cuantificaremos en la lección 02-02.

Solución 3. Llamadas: igual que contar_paradas_recursivo, una por tamaño n, n−1, ..., 0 → n+1 llamadas. Coste de cada llamada de tamaño k: el slice paradas[1:] cuesta O(k) y además la concatenación lista + [x] crea una lista nueva copiando los k−1 elementos ya invertidos: otro O(k). Total por llamada: O(k). Sumando k = n, n−1, ..., 1: suma aritmética → O(n²). La inversión iterativa (recorrer de atrás adelante con append, o directamente paradas[::-1], que copia una sola vez) es O(n).

Ya sabemos calcular, y no solo nombrar, la complejidad temporal de un algoritmo. El método cabe en cuatro reglas: las operaciones elementales cuestan O(1); el código en secuencia suma; los bucles multiplican por sus iteraciones (y cuando el bucle interno depende del externo, aparece la suma aritmética n(n−1)/2 → O(n²)); y las llamadas a funciones cuestan lo que cuesta su cuerpo — también las recursivas, donde contamos llamadas y multiplicamos por el coste de cada una. Con ese método hemos confirmado que parada_mas_cercana es O(n), hemos visto nacer el O(n²) en los pares de paradas conectables y hemos destapado los costes ocultos de Python: el in sobre listas, los slices y la concatenación de strings, capaces de convertir un aparente O(n) en un O(n²) real. Todo ello, recuerda, midiendo el peor caso.

Pero el tiempo es solo la mitad de la factura. Al sustituir una lista por un set para acelerar transbordos, o al ver que cada llamada recursiva apila una copia de la lista, hemos estado pagando con memoria sin contabilizarlo. En la próxima lección (02-02) aprenderemos a hacer exactamente el mismo análisis línea a línea, pero midiendo bytes en lugar de pasos: la complejidad espacial.