Fenómeno

Dos programas, mismo trabajo, tiempos muy distintos

Dos programas leen un millón de líneas y las agregan al final de un array que crece solo. El primero termina en un instante. El segundo tarda minutos. La única diferencia está en una línea: cuánto crece la capacidad cuando el array se llena.

En la realocación viste que crecer obliga a copiar todos los valores al bloque nuevo. Si eso pasa en cada inserción, el trabajo se acumula. ¿Cuántas veces hay que crecer para llegar a un millón?

Piensa antes de seguir: si la capacidad crece de uno en uno, ¿cuántas copias hace falta en total para un millón de valores?