Jaká je časová složitost operace přidání prvku na konec pole typu ArrayList?

Časová složitost přidání prvku na konec pole typu ArrayList je v průměru O(1) — amortizovaná konstantní doba.

K tomu dochází, protože ArrayList ukládá prvky v pevně velikém poli. Když přidáváme prvek a v poli je volné místo, prvek se jednoduše vloží do další buňky.

Pokud je však pole plné, provádí se operace rozšíření — vytvoří se nové větší pole a všechny prvky se do něj zkopírují. Tato operace zabere O(n) času, kde n je počet prvků.

Příklad:

ArrayList<Integer> list = new ArrayList<>();
list.add(1); // O(1)
list.add(2); // O(1)
// Při dosažení kapacity pole dojde k rozšíření — O(n)

Celkově je průměrná složitost přidání — O(1), ale v nejhorším případě — O(n).