Временная сложность добавления элемента в конец массива типа ArrayList в среднем составляет O(1) — амортизированное константное время.

Это происходит потому, что ArrayList хранит элементы в массиве фиксированного размера. Когда добавляем элемент, если в массиве есть свободное место, элемент просто помещается в следующую ячейку.

Однако, если массив заполнен, происходит операция расширения — создаётся новый массив большего размера, и все элементы копируются в него. Эта операция занимает O(n) времени, где n — количество элементов.

Пример:

ArrayList<Integer> list = new ArrayList<>();
list.add(1); // O(1)
list.add(2); // O(1)
// При достижении ёмкости массива происходит расширение — O(n)

Таким образом, средняя сложность добавления — O(1), но в худшем случае — O(n).

Какова временная сложность операции добавления элемента в конец массива типа ArrayList?