Aká je časová zložitosť operácie vloženia prvku na začiatok dynamického poľa ArrayList?

Vkladanie prvku na začiatok dynamického poľa (napríklad, ArrayList v Jave) má časovú zložitosť O(n), kde n je počet prvkov v poli.

To je spôsobené tým, že pri vkladaní na začiatok je potrebné posunúť všetky existujúce prvky o jednu pozíciu doprava, aby sa uvoľnilo miesto pre nový prvok. Proces kopírovania prvkov sám o sebe trvá lineárny čas.

Príklad:

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

// Vloženie na začiatok
list.add(0, 0); // posunie všetky prvky doprava

Preto je vkladanie na koniec zvyčajne rýchlejšie (amortizované O(1)), zatiaľ čo na začiatok je O(n).