Mekkora az időbeli komplexitású az ArrayList típusú tömb végére elem hozzáadása?

Az ArrayList típusú tömb végére történő elem hozzáadásának átlagos időkomplexitása O(1) — amortizált állandó idő.

Ez azért van, mert az ArrayList az elemeket egy fix méretű tömbben tárolja. Amikor hozzáadunk egy elemet, és van szabad hely a tömbben, az elem egyszerűen a következő helyre kerül.

Azonban, ha a tömb megtelt, akkor egy bővítési művelet történik — egy nagyobb méretű új tömb jön létre, és minden elemet átmásolnak bele. Ez a művelet O(n) időt vesz igénybe, ahol n az elemek száma.

Példa:

ArrayList<Integer> list = new ArrayList<>();
list.add(1); // O(1)
list.add(2); // O(1)
// Amikor a tömb kapacitása eléri a határt, bővítés történik — O(n)

Így az átlagos hozzáadási idő — O(1), de a legrosszabb esetben — O(n).