Comparación de modelos

Crecer justo o dejar margen

Compara añadir ocho elementos desde una secuencia vacía, contando solo traslados de elementos existentes.

Crecimiento exacto: reservas 1, 2, 3… posiciones. Las mudanzas trasladan 0 + 1 + 2 + … + 7 = 28 elementos.

Duplicación desde capacidad 1: reservas 1, 2, 4 y 8. Trasladas 0 + 1 + 2 + 4 = 7 elementos. Queda espacio sin usar entre crecimientos.

Este ejemplo empieza en capacidad 1 para aislar la comparación. La figura de enteros puede empezar en capacidad 4. Son dos escenarios distintos, no una discrepancia de la regla.

En la figura, las barras cuentan los elementos trasladados en cada una de las ocho inserciones, con la misma escala.

La segunda estrategia intercambia capacidad libre por menos mudanzas; no elimina el coste de una inserción que provoca crecimiento.