Kāda ir sliktākā add() metodes izpildes laiks ArrayList?

Amortizēts pastāvīgs laiks O(1).

Lielākajā daļā gadījumu add() tiek izpildīts pastāvīgā laikā, jo jauns elements vienkārši tiek pievienots esošā iekšējā masīva beigās.

Sliktākais gadījums ir tad, kad sasniegta iekšējā masīva ietilpība. Šajā gadījumā ArrayList izveido jaunu, lielāku masīvu (parasti 1,5 reizes lielāku par pašreizējo), pārkopē visus elementus no vecā masīva uz jauno un pēc tam pievieno jauno elementu. Šī pārkopēšanas operācija aizņem laiku proporcionālu pašreizējam elementu skaitam (N), kas noved pie laika sarežģītības O(N).

Tomēr, tā kā šādas izmēra izmaiņas notiek reti un ir izplatītas daudzās add() izsaukumos, vidējais add() izpildes laiks (amortizēts) paliek pastāvīgs.