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

Временная сложность добавления элемента в ArrayList обычно амортизированно O(1). Это связано с тем, что:

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

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

Пример:

ArrayList<Integer> list = new ArrayList<>();
list.add(10); // O(1) амортизированно