Koja je vremenska složenost operacije dodavanja elementa na kraj niza tipa ArrayList?

Vremenska složenost dodavanja elementa na kraj niza tipa ArrayList u proseku je O(1) — amortizovano konstantno vreme.

To se dešava zato što ArrayList čuva elemente u fiksnom veličinskom nizu. Kada dodajemo element i u nizu postoji slobodno mesto, element se jednostavno smešta u sledeću ćošku.

Međutim, ako je niz popunjen, vrši se operacija proširenja — kreira se novi, veći niz i svi elementi se kopiraju u njega. Ova operacija traje O(n) vremena, gde je n broj elemenata.

Primer:

ArrayList<Integer> list = new ArrayList<>();
list.add(1); // O(1)
list.add(2); // O(1)
// Kada se dostigne kapacitet niza, vrši se proširenje — O(n)

Dakle, prosečna složenost dodavanja je — O(1), ali u najgorem slučaju — O(n).