Kā tiek noteikta laika sarežģītība, pievienojot elementu uz ArrayList?

ArrayList elementa pievienošanas laika sarežģītība parasti ir amortizēta līdz O(1). Tas ir tāpēc, ka:

• Ja ArrayList iekšējais masīvs ir brīvs vieta, jauns elements vienkārši tiek ierakstīts nākamajā pozīcijā — operācija aizņem nemainīgu laiku O(1).
• Ja iekšējais masīvs ir pilns, tas tiek paplašināts: tiek izveidots jauns lielāks masīvs, un visi elementi tiek pārvietoti tur. Šī operācija aizņem O(n) laiku, kur n ir pašreizējais saraksta lielums.

Tomēr paplašināšana nenotiek katru reizi, bet periodiski, tāpēc vidējā (amortizētā) pievienošanas sarežģītība paliek O(1).

Piemērs:

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