Care este complexitatea temporală a operației de adăugare a unui element la sfârșitul unui array de tip ArrayList?

Complexitatea temporală de adăugare a unui element la sfârșitul unui array de tip ArrayList în medie este O(1) — timp amortizat constant.

Acest lucru se întâmplă deoarece ArrayList stochează elementele într-un array de dimensiune fixă. Când adăugăm un element și există spațiu liber în array, elementul este pur și simplu plasat în următoarea celulă.

Totuși, dacă array-ul este plin, are loc o operație de extindere — se creează un nou array de dimensiune mai mare și toate elementele sunt copiate în el. Această operație durează O(n) timp, unde n este numărul de elemente.

Exemplu:

ArrayList<Integer> list = new ArrayList<>();
list.add(1); // O(1)
list.add(2); // O(1)
// Când se atinge capacitatea array-ului, are loc o extindere — O(n)

Prin urmare, complexitatea medie a adăugării este — O(1), dar în cel mai rău caz — O(n).