Jaká je nejhorší doba běhu metody add() pro ArrayList?

Amortizovaný stálý čas O(1).

Ve většině případů se add() provádí v konstantním čase, protože nový prvek je jednoduše přidán na konec existujícího vnitřního pole.

Nejhorší případ nastává, když je dosažena kapacita vnitřního pole. V tomto případě ArrayList vytvoří nové větší pole (obvykle 1,5krát větší než současné), zkopíruje všechny prvky ze starého pole do nového a poté přidá nový prvek. Tato kopírovací operace trvá čas úměrný aktuálnímu počtu prvků (N), což vede k časové složitosti O(N).

Nicméně, protože takové změny velikosti se dějí zřídka a jsou rozloženy přes mnoho volání add(), průměrný čas provedení add() (amortizovaný) zůstává konstantní.