Koje je najgore vreme izvršavanja metode add() za ArrayList?

A amortizovano konstantno vreme O(1).

U većini slučajeva, add() se izvršava u konstantnom vremenu, jer se novi element jednostavno dodaje na kraj postojećeg unutrašnjeg niza.

Najgori slučaj nastaje kada se dostigne kapacitet unutrašnjeg niza. U tom slučaju, ArrayList kreira novi, veći niz (obično 1,5 puta veći od trenutnog), kopira sve elemente iz starog niza u novi i zatim dodaje novi element. Ova operacija kopiranja traje vreme proporcionalno trenutnom broju elemenata (N), što dovodi do vremenske složenosti O(N).

Međutim, pošto se takve promene veličine retko dešavaju i raspoređene su preko mnogo poziva add(), prosečno vreme izvršavanja add() (amortizovano) ostaje konstantno.