Care este complexitatea temporală a operației de inserare a unui element la începutul unui ArrayList dinamic?

Inserarea unui element la începutul unui array dinamic (de exemplu, ArrayList în Java) are o complexitate temporară de O(n), unde n este numărul de elemente din array.

Acest lucru se datorează faptului că, la inserarea la început, toate elementele existente trebuie mutate cu o poziție spre dreapta pentru a face loc pentru noul element. Procesul de copiere a elementelor în sine durează timp liniar.

Exemplu:

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

// Inserare la început
list.add(0, 0); // mută toate elementele spre dreapta

Prin urmare, inserarea la sfârșit este de obicei mai rapidă (amortizat O(1)), în timp ce la început este O(n).