Jak określa się złożoność czasową podczas dodawania elementu do ArrayList?

Złożoność czasowa dodania elementu do ArrayList jest zazwyczaj amortyzowana do O(1). Wynika to z faktu, że:

• Jeśli wewnętrzna tablica ArrayList ma wolne miejsce, nowy element jest po prostu zapisywany na następną pozycję — operacja ta zajmuje czas stały O(1).
• Jeśli wewnętrzna tablica jest pełna, następuje jej rozszerzenie: tworzona jest nowa tablica większego rozmiaru, a wszystkie elementy są kopiowane do niej. Ta operacja zajmuje O(n), gdzie n to obecny rozmiar listy.

Jednak rozszerzenie nie zachodzi przy każdym dodaniu, lecz okresowo, więc średnia (amortyzowana) złożoność dodawania pozostaje O(1).

Przykład:

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