W jakich sytuacjach dodanie elementu na koniec ArrayList może mieć złożoność czasową O(n)?

Dodanie elementu na koniec ArrayList zazwyczaj ma amortyzowaną złożoność czasową O(1), ale w niektórych przypadkach może to być O(n). Dzieje się tak, gdy wewnętrzna tablica przechowująca elementy jest pełna i konieczne jest jej powiększenie.

Przy dodawaniu nowego elementu:

• Jeśli jest miejsce, element jest po prostu dodawany — O(1).
• Jeśli miejsca nie ma, tworzy się nową tablicę większego rozmiaru (zwykle 1,5-2 razy większą), a wszystkie istniejące elementy są kopiowane do nowej tablicy — ta operacja jest O(n).

W związku z tym, dodanie elementu może mieć złożoność czasową O(n) dokładnie w momencie powiększania wewnętrznej tablicy.