Kaip nustatoma laiko sudėtingumas pridedant elementą į ArrayList?

ArrayList elemento pridėjimo laiko sudėtingumas paprastai yra amortizuotas iki O(1). Tai yra dėl to, kad:

• Jei ArrayList vidinis masyvas turi laisvos vietos, naujas elementas paprasčiausiai įrašomas į kitą poziciją — operacija užtrunka pastovų laiką O(1).
• Jei vidinis masyvas užpildytas, jis plečiasi: kuriamas naujas didesnis masyvas, ir visi elementai kopijuojami į jį. Ši operacija užtrunka O(n), kur n yra dabartinis sąrašo dydis.

Tačiau, plečiasi ne kiekvieną kartą, o periodiškai, todėl vidutinė (amortizuota) pridėjimo sudėtingumas išlieka O(1).

Pavyzdys:

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