Kādās situācijās elementa pievienošana ArrayList beigām var būt ar laika sarežģītību O(n)?

Elementa pievienošana ArrayList galvenokārt ir amortizēta laika sarežģītība O(1), bet dažos gadījumos tas var būt O(n). Tas notiek, kad iekšējais masīvs, kas glabā elementus, ir pilns un nepieciešams to paplašināt.

Pievienojot jaunu elementu:

• Ja ir vieta, elements tiek vienkārši pievienots — O(1).
• Ja vieta nav, tiek izveidots jauns masīvs ar lielāku izmēru (parasti 1,5-2 reizes lielāks), un visi esošie elementi tiek kopēti jaunajā masīvā — šī operācija ir O(n).

Tādēļ elementa pievienošana var būt O(n) tieši brīdī, kad tiek paplašināts iekšējais masīvs.