Mi a legrosszabb futási idő az add() metódushoz az ArrayList esetében?

Átlagolt állandó idő O(1).

A legtöbb esetben a add() végrehajtása állandó időt vesz igénybe, mivel az új elem egyszerűen hozzáadódik a meglévő belső tömb végéhez.

A legrosszabb eset akkor fordul elő, amikor eléri a belső tömb kapacitását. Ebben az esetben az ArrayList létrehoz egy új, nagyobb tömböt (általában az aktuális méret 1,5-szerese), átmásolja az összes elemet a régi tömbből az újjá, majd hozzáadja az új elemet. Ez az átmásolási művelet időt vesz igénybe, arányosan az aktuális elemek számával (N), ami O(N) időbonyolultsághoz vezet.

Azonban, mivel ilyen méretváltozások ritkán fordulnak elő, és sok add() hívás között oszlanak meg, az add() átlagos végrehajtási ideje (amortizált) állandó marad.