Aká je časová zložitosť operácie pridania prvku na koniec poľa typu ArrayList?

Časová zložitosť pridania prvku na koniec poľa typu ArrayList je v priemere O(1) — amortizovaná konštantná doba.

K tomu dochádza, pretože ArrayList uchováva prvky v pevne veľkom poli. Keď pridávame prvok a v poli je voľné miesto, prvok sa jednoducho vloží do ďalšej bunky.

Ak je však pole plné, vykoná sa operácia rozšírenia — vytvorí sa nové väčšie pole a všetky prvky sa do neho skopírujú. Táto operácia trvá O(n) času, kde n je počet prvkov.

Príklad:

ArrayList<Integer> list = new ArrayList<>();
list.add(1); // O(1)
list.add(2); // O(1)
// Pri dosiahnutí kapacity poľa dôjde k rozšíreniu — O(n)

Celkovo je priemerná zložitosť pridania — O(1), ale v najhoršom prípade — O(n).