Hogyan határozzuk meg az időbeli összetettséget egy elem hozzáadásakor az ArrayList-hez?

Az ArrayList-hez elem hozzáadásának időkomplexitása általában amortizáltan O(1). Ez abból adódik, hogy:

• Ha az ArrayList belső tömbjében van szabad hely, az új elem egyszerűen a következő pozícióba kerül — az művelet konstans időt vesz igénybe O(1).
• Ha a belső tömb megtelt, akkor bővítés történik: egy nagyobb méretű új tömb készül, és minden elem átkerül oda. Ez a művelet O(n) időt vesz igénybe, ahol n a lista aktuális mérete.

Azonban a bővítés nem minden hozzáadáskor történik, hanem időszakosan, így a hozzáadás átlagos (amortizált) komplexitása továbbra is O(1).

Példa:

ArrayList<Integer> list = new ArrayList<>();
list.add(10); // Amortizált O(1)