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

Добавление элемента в конец ArrayList в среднем имеет амортизированную сложность O(1). Это связано с тем, что при добавлении элемент просто помещается в следующую свободную ячейку массива.

Однако, если внутренний массив заполнен, происходит его расширение (обычно в 1.5-2 раза), что требует копирования всех элементов в новый массив. В этот момент операция добавления занимает O(n), где n — текущий размер списка.

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