Jaka jest złożoność czasowa operacji dodawania elementu na koniec tablicy typu ArrayList?

Złożoność czasowa dodania elementu na koniec tablicy typu ArrayList średnio wynosi O(1) — amortyzowany czas stały.

Dzieje się tak, ponieważ ArrayList przechowuje elementy w tablicy o stałym rozmiarze. Gdy dodajemy element i w tablicy jest wolne miejsce, element jest po prostu umieszczany w następnej komórce.

Jednak jeśli tablica jest pełna, następuje operacja rozszerzenia — tworzy się nowa, większa tablica, a wszystkie elementy są do niej kopiowane. Ta operacja zajmuje O(n) czasu, gdzie n to liczba elementów.

Przykład:

ArrayList<Integer> list = new ArrayList<>();
list.add(1); // O(1)
list.add(2); // O(1)
// Gdy osiągnięta jest pojemność tablicy, następuje rozszerzenie — O(n)

W związku z tym, średnia złożoność dodawania to — O(1), ale w najgorszym przypadku — O(n).