U kojim situacijama dodavanje elementa na kraj ArrayList može imati vremensku složenost O(n)?

Dodavanje elementa na kraj ArrayList obično ima amortizovanu vremensku složenost O(1), ali u nekim slučajevima može biti O(n). To se dešava kada je unutrašnji niz koji čuva elemente pun i potrebno ga je proširiti.

Prilikom dodavanja novog elementa:

• Ako ima mesta, element se jednostavno dodaje — O(1).
• Ako nema mesta, kreira se novi niz veće veličine (obično 1,5-2 puta veći), i svi postojeći elementi se kopiraju u novi niz — ta operacija je O(n).

Dakle, dodavanje elementa može imati vremensku složenost O(n) baš u trenutku proširenja unutrašnjeg niza.