Care este complexitatea temporală a operației de inserare a unui element în partea mediană a unui array implementat prin ArrayList?

Inserarea unui element în partea mediană a unui array implementat prin ArrayList necesită deplasarea tuturor elementelor ulterioare spre dreapta pentru a face loc pentru noul element. Aceasta înseamnă că operațiunea de inserare are o complexitate temporară de O(n), unde n este numărul de elemente care trebuie mutate. În cel mai rău caz (inserarea la început), aproape toate elementele array-ului sunt mutate.