Kedy operácia vloženia prvku do poľa vedie k dobe behu úmernej veľkosti poľa?

Operácia vloženia prvku do poľa spôsobí dobu behu úmernú veľkosti poľa, keď je pole implementované ako dynamické pole a dôjde k prealokácii pamäte (realloc). Napríklad, ak je pole plné a je potrebné pridať nový prvok, vytvorí sa nové väčšie pole a všetky prvky sa skopírujú zo starého do nového. Tento proces kopírovania trvá čas úmerný počtu prvkov v poli.

Tiež, ak vloženie nie je na konci poľa, ale do stredu alebo na začiatok, všetky nasledujúce prvky musia byť posunuté, čo tiež vyžaduje čas úmerný počtu posunutých prvkov.