Aký je najhorší čas vykonávania metódy add() pre ArrayList?

Amortizované konštantné časové O(1).

Vo väčšine prípadov sa add() vykonáva v konštantnom čase, pretože nový prvok sa jednoducho pridá na koniec existujúceho vnútorného poľa.

Najhorší prípad nastáva, keď sa dosiahne kapacita vnútorného poľa. V tomto prípade ArrayList vytvorí nové, väčšie pole (zvyčajne 1,5-krát väčšie ako aktuálne), skopíruje všetky prvky zo starého poľa do nového a potom pridá nový prvok. Táto operácia kopírovania trvá čas úmerný aktuálnemu počtu prvkov (N), čo vedie k časovej zložitosti O(N).

Avšak, pretože takéto zmeny veľkosti sa dejú zriedka a sú rozložené na mnoho volaní add(), priemerný čas vykonávania add() (amortizovaný) zostáva konštantný.