În ce situații adăugarea unui element la sfârșitul unui ArrayList poate avea o complexitate de timp O(n)?

Adăugarea unui element la sfârșitul unui ArrayList are, în general, o complexitate temporară amortizată de O(1), dar în unele cazuri poate fi O(n). Acest lucru se întâmplă atunci când array-ul intern care stochează elementele este plin și trebuie extins.

La adăugarea unui nou element:

• Dacă există spațiu, elementul este pur și simplu adăugat — O(1).
• Dacă nu există spațiu, se creează un nou array de dimensiuni mai mari (de obicei de 1,5-2 ori mai mare), și toți elementele existente sunt copiate în noul array — această operație este O(n).

Prin urmare, adăugarea unui element poate avea o complexitate temporară de O(n) chiar în momentul extinderii array-ului intern.