Jaká je časová složitost operace vložení prvku na začátek dynamického pole ArrayList?

Vložení prvku na začátek dynamického pole (například ArrayList v Javě) má časovou složitost O(n), kde n je počet prvků v poli.

To je způsobeno tím, že při vkládání na začátek je třeba posunout všechny stávající prvky o jednu pozici doprava, aby se uvolnilo místo pro nový prvek. Samotný proces kopírování prvků trvá lineární čas.

Příklad:

ArrayList<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);

// Vložení na začátek
list.add(0, 0); // posune všechny prvky doprava

Proto je vložení na konec obvykle rychlejší (amortizovaně O(1)), zatímco na začátek je O(n).