Ako sa určuje časová zložitosť pri pridávaní prvku do ArrayList?

Časová zložitosť pridania prvku do ArrayList je običajno amortizirana na O(1). To je zato, ker:

• Če ima notranji niz ArrayList prostega prostora, se nov element preprosto zapiše na naslednjo pozicijo — operacija traja konstantni čas O(1).
• Če je notranji niz poln, pride do njegove razširitve: ustvarjen je nov večji niz in vsi elementi se vanj kopirajo. Ta operacija traja O(n), kjer je n trenutna velikost seznama.

Vendar se razširitev ne zgodi pri vsakem dodajanju, temveč periodično, zato povprečna (amortizirana) kompleksnost dodajanja ostaja O(1).

Primer:

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