En las dos lecciones anteriores analizamos tiempo y espacio "asumiendo el peor caso", y varias veces nos cruzamos con funciones que a veces terminan enseguida y a veces recorren toda la entrada: hay_duplicadas cortaba al encontrar el primer duplicado, todas_antes_b al encontrar la primera llegada tardía. Esta lección pone nombre y método a esa observación: un mismo algoritmo puede tener costes muy distintos según qué entrada reciba, no solo según su tamaño. Aprenderemos a definir y calcular el mejor caso, el peor caso y el caso promedio, a decidir cuál importa según el contexto (no es el mismo para una app móvil que para un sistema de frenado), a relacionarlos correctamente con las notaciones O/Ω/Θ — desmontando un mito muy extendido — y a entender de forma intuitiva el análisis amortizado, ese "O(1) amortizado" que dejamos pendiente en la tabla de costes de Python de 02-01.

1. Un algoritmo, muchas entradas: los tres casos
2. Los tres casos de buscar_parada
3. ¿Qué caso importa? Depende del contexto
4. Casos y notaciones: desmontando el mito "O = peor caso"
5. Análisis amortizado: el caso de list.append
6. Ejemplo integrador: validar los horarios de RutaBus

Hasta ahora escribíamos T(n) como si el tamaño n determinara el coste. Pero para muchos algoritmos no es así: dos entradas del mismo tamaño pueden costar muy distinto. Buscar "Plaza Mayor" en una línea de 40 paradas cuesta 1 comparación si es la primera parada y 40 si es la última. El tamaño es idéntico; el coste, no.

Por eso el análisis se desdobla en tres preguntas, las tres sobre entradas de tamaño n:

• Mejor caso: de todas las entradas de tamaño n, ¿cuánto cuesta la más favorable? Es el suelo del algoritmo: nunca irá más rápido.
• Peor caso: ¿cuánto cuesta la entrada más desfavorable? Es el techo: una garantía absoluta, pase lo que pase.
• Caso promedio: si las entradas llegan según una distribución dada (típicamente "todas igual de probables"), ¿cuánto cuesta en media? Es la expectativa realista a largo plazo.

Tres detalles de la definición que evitan confusiones después:

1. Los tres casos se refieren a la entrada, no a la suerte del algoritmo: el mejor caso de una búsqueda no es "tener un ordenador rápido", es "que lo buscado esté en la primera posición".
2. Los tres son funciones de n: T_mejor(n), T_peor(n), T_promedio(n). El mejor caso de buscar en 40 paradas y en 4.000 es "está la primera", pero sigue siendo una función (constante) del tamaño.
3. El caso promedio exige declarar una distribución de probabilidad sobre las entradas ("la parada buscada puede estar en cualquier posición con igual probabilidad"). Si la distribución supuesta no se parece a la realidad, el promedio calculado tampoco.

Apliquémoslo a la búsqueda lineal de la lección 01-02, la que usa RutaBus para localizar una parada en una línea:

Operación básica: la comparación parada == nombre. Sea n = len(linea).

Mejor caso — O(1). La entrada más favorable: nombre está en la primera posición. Una comparación y return. T_mejor(n) = 1, constante: Θ(1), sea cual sea n.

Peor caso — O(n). Las entradas más desfavorables: nombre está en la última posición (n comparaciones) o no está (n comparaciones y return -1). T_peor(n) = n: Θ(n). Es la garantía que dábamos por defecto en 02-01.

Caso promedio — O(n). Supongamos que la parada está en la línea y que cada una de las n posiciones es igual de probable (probabilidad 1/n cada una). Si está en la posición i (contando desde 1), cuestan i comparaciones. El coste medio es la media de todos los escenarios ponderada por su probabilidad:

El numerador es nuestra vieja amiga la suma aritmética (02-01): n(n+1)/2. Dividiendo entre n:

En media, la búsqueda recorre media línea. ¿Y asintóticamente? n/2 es lineal — las constantes se descartan (01-03) —, así que el caso promedio es Θ(n), el mismo orden que el peor caso. Es un resultado muy instructivo: "el doble de rápido en la práctica" y "del mismo orden en teoría" son afirmaciones compatibles. Y si las búsquedas fallidas fueran frecuentes (usuarios que escriben mal el nombre), el promedio real se acercaría aún más a n — recuerda: el promedio depende de la distribución que declares.

Resumen:

Los tres análisis existen porque responden a necesidades distintas. La pregunta correcta no es "¿cuál es el bueno?" sino "¿qué necesito garantizar?":

Reglas prácticas:

• El peor caso es el análisis por defecto (por eso lo asumimos en 02-01): es el único que da una garantía incondicional, suele ser el más fácil de calcular y nunca peca de optimista.
• El caso promedio es el más informativo cuando hay volumen: a un servicio que atiende un millón de búsquedas al día le importa el coste medio × un millón, no la búsqueda concreta más lenta. Su debilidad: depende de una distribución supuesta que puede no cumplirse.
• El mejor caso, aislado, es casi propaganda: "mi algoritmo puede terminar en O(1)" no compromete a nada (¡también buscar_parada puede!). Solo es valioso cuando sabes que las entradas favorables son las frecuentes en tu sistema.

El ejemplo célebre de esta tensión es quick sort (lo estudiaremos en 04-04): promedio O(n log n) excelente que lo hace dominar en la práctica, peor caso O(n²) que obliga a precauciones. Buena parte de la ingeniería de algoritmos consiste en gestionar esa brecha entre promedio y peor caso.

Circula por internet (y por algún material de formación antiguo — incluida una versión anterior de este curso) una simplificación falsa:

❌ "O grande describe el peor caso, Ω el mejor caso y Θ el caso promedio."

No. Son dos ejes independientes que se combinan:

• Los casos (mejor / peor / promedio) eligen qué función de coste estamos midiendo: T_mejor(n), T_peor(n) o T_promedio(n). Hablan de entradas.
• Las notaciones (O / Ω / Θ, lección 01-03) describen cómo crece una función: cota superior, cota inferior o cota ajustada. Hablan de funciones, sea cual sea.

Cualquier notación puede aplicarse a cualquier caso. Todas estas frases sobre buscar_parada son correctas y significan cosas distintas:

¿De dónde viene la confusión? De un uso coloquial legítimo: como T_mejor(n) ≤ T(n) ≤ T_peor(n) para toda entrada, decir "el algoritmo es O(n)" a secas suele querer decir "ni siquiera su peor caso supera lo lineal", y "es Ω(1)" suele referirse a que su mejor caso es constante. El atajo es cómodo, pero fusiona los dos ejes y acaba produciendo el mito. Dos consecuencias prácticas de tenerlo claro:

• Lo más informativo es Θ aplicado a un caso concreto: "peor caso Θ(n), mejor caso Θ(1)" dice más que cualquier O suelta.
• Frases como "búsqueda lineal es O(n²)" son técnicamente ciertas (una cota superior floja sigue siendo cota superior, como vimos en 01-03) pero inútiles. Si alguien te da solo una O, pregúntate: ¿de qué caso habla, y es una cota ajustada?

En la tabla de costes de 02-01 escribimos que lista.append(x) es "O(1) amortizado", y prometimos explicarlo aquí. El análisis amortizado es una cuarta perspectiva, distinta de las tres anteriores: no promedia sobre entradas posibles, sino sobre una secuencia de operaciones ejecutadas de verdad, una tras otra.

El problema: una lista de Python guarda sus elementos en un bloque de memoria contiguo con una capacidad fija. Mientras quede hueco, append escribe al final: O(1) auténtico. Pero cuando el bloque se llena, Python reserva otro más grande (aproximadamente un 12,5% mayor, más un margen) y copia todos los elementos: ese append concreto cuesta O(n).

¿Es entonces append O(n)? Mirando una operación aislada en su peor caso, sí. Pero es una respuesta engañosa, porque las operaciones caras no pueden ocurrir seguidas: tras cada copia costosa, la capacidad sobrante garantiza muchos appends baratos antes de la siguiente. La contabilidad honesta mira la secuencia completa:

• Insertar n elementos empezando por una lista vacía dispara redimensionados de tamaños que crecen geométricamente (cada uno un factor mayor que el anterior).
• La suma de todas las copias de todos los redimensionados es proporcional a n — una serie geométrica se comporta como su último término, no como la suma aritmética de 02-01.
• Coste total: n appends baratos + O(n) de copias acumuladas = O(n). Repartido entre las n operaciones: O(1) por operación.

Eso significa "O(1) amortizado": garantía sobre el total de la secuencia — n appends cuestan O(n), seguro, sin suposiciones probabilísticas —, aunque alguna operación suelta sea cara. Una metáfora contable: cada append barato "paga" un pequeño recargo que queda ahorrado para financiar la copia futura; cuando la copia llega, el fondo la cubre.

En qué se diferencia del caso promedio, que es con lo que más se confunde:

Aviso práctico: "amortizado" garantiza el total, no cada operación individual. En el ejemplo de las llegadas en tiempo real, un append ocasional lento es invisible; en un sistema de tiempo real estricto (tabla del apartado 3), ese pico aislado puede ser inaceptable aunque la media sea perfecta — otra vez, saber qué garantiza cada análisis es lo que permite elegir bien.

Cerremos el módulo juntando todo. El equipo de operaciones de RutaBus carga cada noche el fichero de horarios del día siguiente: una tabla donde cada fila es (linea, parada, hora). Antes de publicarla hay que validarla: ninguna hora puede estar mal formada.

Análisis completo, con n = número de filas:

• Mejor caso — Θ(1): la primera fila ya es inválida (por ejemplo ("L1", "Plaza Mayor", "25:70")). Una comprobación y fuera. Fíjate en la ironía: el mejor caso del algoritmo es el peor día del operador.
• Peor caso — Θ(n): el fichero es completamente válido — hay que mirarlo entero para poder garantizarlo — o el único error está en la última fila. Y este es el caso que importa aquí: el proceso nocturno debe tener un hueco reservado suficiente todas las noches, y las noches normales (fichero correcto) son precisamente las de coste máximo.
• Caso promedio: depende de la distribución de errores. Si las filas son válidas con probabilidad muy alta (lo normal en producción), el caso típico ≈ el peor: Θ(n). Si el fichero viniera plagado de errores tempranos, el promedio bajaría — pero planificar la ventana nocturna con esa esperanza sería mala ingeniería: para dimensionar, peor caso.
• Espacio (02-02): variables escalares reutilizadas, sin copias ni estructuras: auxiliar O(1). Un validador puede permitirse leer y descartar.
• Y si además el validador acumulara las filas correctas en una lista de salida con append, ese coste sería O(1) amortizado por fila: total Θ(n) garantizado.

Un solo algoritmo de diez líneas y hemos usado todo el módulo: análisis línea a línea, casos, notaciones bien aplicadas, espacio y amortización.

• Repetir el mito "O = peor caso, Ω = mejor caso": los casos eligen la función a medir; las notaciones describen su crecimiento. Se combinan libremente: "mejor caso O(1)" y "peor caso Ω(n)" son frases perfectamente formadas.
• Confundir mejor caso con entrada pequeña: el mejor caso no es "n = 1"; es la entrada de tamaño n más favorable. Los tres casos son funciones de n.
• Dar un caso promedio sin declarar la distribución: "en promedio n/2" presupone posiciones equiprobables y que el elemento está. Cambia la premisa (muchas búsquedas fallidas) y cambia el promedio. Sin distribución explícita, un promedio no afirma nada.
• Vender el mejor caso: "puede llegar a O(1)" es cierto para casi cualquier búsqueda con salida temprana y no garantiza nada. Sospecha de cualquier análisis que solo mencione el escenario favorable.
• Leer "amortizado" como "siempre": O(1) amortizado promete el total de la secuencia, no cada operación; alguna puede ser O(n). Irrelevante en una app, decisivo en tiempo real.
• Consejo: al analizar un algoritmo con salidas tempranas (return dentro del bucle), pregúntate sistemáticamente tres cosas: ¿qué entrada me hace salir a la primera? (mejor caso), ¿cuál me obliga a llegar al final? (peor caso), ¿cómo llegan las entradas en mi sistema? (caso que debo optimizar).

Ejercicio 1. RutaBus comprueba si dos usuarios pueden compartir trayecto verificando si sus líneas tienen alguna parada común, con la versión O(n²) de 02-01:

Suponiendo len(linea_a) = len(linea_b) = n, describe la entrada del mejor caso y la del peor caso, y da el orden de cada uno.

Ejercicio 2. Clasifica cada afirmación como verdadera o falsa, justificando con los dos ejes (casos vs notaciones): a) "El mejor caso de buscar_parada es O(n)." b) "El peor caso de buscar_parada es Ω(n)." c) "buscar_parada es Θ(n) para toda entrada." d) "El caso promedio de buscar_parada es O(n²)."

Ejercicio 3. El panel de una parada mantiene las llegadas en una lista ordenada por hora insertando cada nueva llegada en su sitio:

Con la tabla de costes de 02-01: (a) da mejor y peor caso de registrar_llegada y qué entrada los provoca; (b) razona si insert puede presumir de "O(1) amortizado" como append, o no, y por qué.

Solución 1. Mejor caso Θ(n) — cuidado, no Θ(1): la entrada más favorable es que la primera parada de linea_a esté en linea_b... pero encontrarla con in puede costar hasta n comparaciones; el caso rigurosamente óptimo es que además sea la primera de linea_b: 1 comparación, Θ(1). Este ejercicio enseña a definir el mejor caso con precisión: la entrada óptima es "primera de A coincide con primera de B" → Θ(1); "primera de A está en B (donde sea)" ya puede costar Θ(n). Peor caso Θ(n²): no comparten ninguna parada — las n vueltas del bucle externo pagan n comparaciones cada una, sin salida temprana posible. Nótese que el peor caso es justamente la respuesta "False", igual que en horario_valido el peor caso era el fichero válido: verificar la ausencia obliga a mirarlo todo.

Solución 2. a) Verdadera. El mejor caso es Θ(1), y toda función Θ(1) es también O(n): una cota superior floja es válida (aunque poco informativa). La frase es correcta; útil, no. b) Verdadera. El peor caso cuesta exactamente n comparaciones, luego está acotado inferiormente por algo lineal: Ω(n). Y también es O(n); por eso lo ajustado es decir Θ(n). c) Falsa. Para la entrada con la parada en primera posición el coste es 1, que no es Θ(n). Precisamente porque los casos difieren, el algoritmo en conjunto no tiene una Θ única — hay que dársela a cada caso. d) Verdadera pero inútil. El promedio es Θ(n) y por tanto también O(n²): cota superior cierta y floja. Es el ejemplo canónico de por qué "es O(algo)" sin más puede ser un dato vacío.

Solución 3. (a) La búsqueda con bisect cuesta O(log n) siempre. El coste variable está en insert: desplaza todos los elementos posteriores a la posición. Mejor caso: la llegada es la más tardía y va al final — 0 desplazamientos — → Θ(log n) total. Peor caso: la llegada es la más temprana y va al principio — n desplazamientos → Θ(n) total. (b) No: la amortización de append funciona porque las operaciones caras (redimensionar) son necesariamente escasas y las baratas las prefinancian. Con insert no existe ese mecanismo: cada inserción al principio cuesta O(n) siempre, y una secuencia adversa (llegadas en orden inverso, de la más tardía a la más temprana... o un atacante, tabla del apartado 3) hace que todas las operaciones sean caras: n inserciones → suma aritmética → Θ(n²) total, es decir Θ(n) por operación también en términos amortizados. "Amortizado" no es un conjuro: hay que demostrar que las operaciones caras no pueden repetirse.

Con esta lección completamos el arsenal del análisis de algoritmos. Hemos aprendido que el coste no depende solo del tamaño de la entrada sino de la entrada misma, y a medirlo con tres reglas distintas sobre buscar_parada: mejor caso Θ(1), peor caso Θ(n) y caso promedio ≈ n/2 → Θ(n); hemos visto que la elección del caso es una decisión de ingeniería — peor caso para garantías, tiempo real y entradas hostiles; promedio para el rendimiento típico a volumen; mejor caso solo cuando lo favorable es lo frecuente —; hemos desmontado el mito "O = peor caso, Ω = mejor caso" separando los dos ejes (los casos eligen qué función medir, las notaciones describen cómo crece); hemos añadido el análisis amortizado con list.append — garantía sobre la secuencia completa, sin probabilidades —; y lo hemos integrado todo validando los horarios nocturnos de RutaBus, donde el peor caso (el fichero correcto) resulta ser el día normal. Junto con el análisis temporal línea a línea (02-01) y el espacial (02-02), ya sabemos responder con rigor a la pregunta "¿cuánto cuesta este algoritmo?" en todas sus variantes.

Pero saber medir algoritmos no es lo mismo que saber crearlos. Hasta ahora hemos analizado soluciones ya escritas; la pregunta natural siguiente es: ante un problema nuevo de RutaBus — planificar el trayecto óptimo entre dos paradas, asignar autobuses a líneas, cuadrar horarios —, ¿cómo se diseña un buen algoritmo desde cero? En el Módulo 3 estudiaremos las cuatro grandes estrategias de diseño que ya asomaron en 01-02: divide y vencerás (03-01), algoritmos voraces (03-02), programación dinámica (03-03) — donde reencontraremos, con nombre propio, la idea de gastar memoria para no repetir trabajo que apuntamos en 02-02 — y backtracking (03-04). Y cada diseño que hagamos lo someteremos al juicio de las herramientas que este módulo nos ha dado.