Cum se determină complexitatea temporală la adăugarea unui element în ArrayList?

Complexitatea temporară de adăugare a unui element în ArrayList este de obicei amortizată la O(1). Acest lucru se datorează faptului că:

• Dacă array-ul intern al ArrayList are spațiu liber, noul element este pur și simplu scris în poziția următoare — operația durează timp constant O(1).
• Dacă array-ul intern este plin, se face o extindere: se creează un nou array de dimensiune mai mare și toate elementele sunt copiate acolo. Această operație durează O(n), unde n este dimensiunea curentă a listei.

Totuși, extinderea nu are loc la fiecare adăugare, ci periodic, astfel încât complexitatea medie (amortizată) a adăugării rămâne O(1).

Exemplu:

ArrayList<Integer> list = new ArrayList<>();
list.add(10); // Amortizat O(1)