Peor caso, promedio y amortizado no son lo mismo

Decir que una operación “normalmente es rápida” puede esconder tres afirmaciones distintas: que la mayoría de las entradas son fáciles, que el azar suele ayudar o que una operación cara ocurre muy pocas veces. Caso promedio y costo amortizado no son sinónimos.

Mejor y peor caso

En una búsqueda lineal, el mejor caso ocurre cuando el objetivo está primero: una sola comparación, $\Theta(1)$. El peor ocurre cuando está último o no aparece: $\Theta(n)$.

El peor caso da una garantía: ninguna entrada de tamaño $n$ puede obligar al algoritmo a hacer más que esa cota. Es especialmente importante cuando una demora excepcional rompe un límite de tiempo, congela una interfaz o deja vencer una operación.

El promedio necesita una distribución

El caso promedio necesita una distribución de probabilidades sobre las entradas. Si el objetivo de una búsqueda lineal está presente y es igualmente probable en cualquier posición, se hacen en promedio

comparaciones. Sigue siendo $\Theta(n)$, aunque la constante sea aproximadamente la mitad del peor caso.

Sin decir qué entradas son probables, “promedio” no está definido. Los datos reales rara vez son uniformes, y una distribución equivocada vuelve irrelevante el cálculo.

Quicksort, donde declarar el caso cambia todo

Quicksort muestra por qué conviene declarar el caso. Si cada pivote divide el arreglo en partes parecidas, hay $\log n$ niveles con $n$ trabajo por nivel: $\Theta(n\log n)$. Si el pivote queda siempre en un extremo, aparecen $n$ niveles: $\Theta(n^2)$.

Elegir el pivote al azar no elimina el peor caso; lo vuelve muy improbable para entradas independientes del azar. La garantía sigue siendo cuadrática, mientras que el costo esperado es $O(n\log n)$. Son dos afirmaciones verdaderas sobre el mismo algoritmo.

El arreglo dinámico y su inserción cara

Un arreglo dinámico suele agregar elementos en $O(1)$, pero cuando se llena necesita reservar un bloque mayor y copiar todo. Esa inserción particular cuesta $O(n)$. ¿Cómo puede decirse entonces que agregar al final es constante?

La respuesta no usa probabilidades. Mira una secuencia completa de operaciones. Si la capacidad se duplica —1, 2, 4, 8— las copias totales antes de guardar $n$ elementos son

Amortizado: el total dividido por las operaciones

Las $n$ inserciones normales cuestan $n$ y todas las redimensiones juntas cuestan menos de $2n$. El trabajo total es menor que $3n$, así que dividido entre $n$ operaciones da una constante por inserción: $O(1)$ amortizado.

No significa que cada llamada tarde lo mismo. Una puede copiar miles de elementos. Significa que no puede ocurrir muchas veces sin que antes hayan ocurrido suficientes operaciones baratas. Las operaciones comunes “pagan” de a poco la cara.

Promedio y amortizado no son lo mismo

El caso promedio promedia sobre entradas posibles y necesita supuestos probabilísticos. El análisis amortizado promedia sobre una secuencia, sin azar: garantiza un costo total incluso si un adversario elige las operaciones.

Una tabla hash suele tener acceso $O(1)$ esperado bajo supuestos sobre la función hash. Un vector dinámico tiene inserción $O(1)$ amortizada aunque la secuencia sea la peor imaginable. La palabra que acompaña al costo cambia qué se está garantizando.

Cuándo el amortizado no alcanza

El costo amortizado puede ser insuficiente cuando importa la latencia de cada operación. Un servidor que responde rápido 999 veces y se frena un segundo en la número 1000 quizá tenga buen promedio y mala experiencia.

En esos casos se reparte el trabajo caro entre varias operaciones, se reserva capacidad antes o se elige una estructura con peor caso acotado. El análisis asintótico no decide la arquitectura solo: hay que preguntar si importa el throughput total o el máximo de cada respuesta.

Cuál de los tres mirar

Cierre

Cuando alguien diga “esta operación es $O(1)$”, la pregunta correcta es: ¿peor caso, esperado o amortizado? El peor caso promete un techo por operación; el promedio depende de una distribución; el amortizado limita una secuencia completa. Nombrar bien la garantía es parte de diseñar bien la estructura.