Coste

La condición del costo

Agregar al final de un array dinámico que duplica:

amortizado: O(1) por inserción;
peor caso de una sola inserción: O(n), cuando toca crecer.

Las dos frases son ciertas a la vez. Decir solo «O(1)» sin «amortizado» no dice toda la verdad.

Mides cada una de 1 000 000 inserciones en un array dinámico que duplica. Casi todas tardan 20 ns y unas 20 tardan más, las más lentas hasta 8 ms. ¿Qué afirmación es correcta?El O(1) amortizado se cumple, y el peor caso de una sola inserción es O(n)El costo es O(log n), porque hubo unas 20 inserciones lentas en un millónEl O(1) amortizado es falso, porque unas inserciones tardan millones de veces másEl costo es O(1) en el peor caso, porque la media por inserción es de unos 20 ns