Milyen helyzetekben lehet az ArrayList végére elem hozzáadása O(n) időkomplexitású?

Az ArrayList végére történő elem hozzáadás általában amortizált időbeli komplexitással O(1), de bizonyos esetekben O(n) is lehet. Ez akkor fordul elő, amikor a belső tömb, amely a elemeket tárolja, megtelt, és bővíteni kell.

Új elem hozzáadásakor:

• Ha van hely, az elem egyszerűen hozzáadódik — O(1).
• Ha nincs hely, akkor egy nagyobb méretű új tömb jön létre (általában 1,5-2 szer nagyobb), és minden meglévő elem átkerül az új tömbbe — ez az művelet O(n).

Ezért az elem hozzáadása pontosan akkor lehet O(n) időbeli komplexitású, amikor a belső tömb bővítésre kerül.