Какая сложность вставки в конец ArrayList и от чего она зависит?

Чтобы корректно ответить на вопрос, важно различать единичную и амортизированную сложность.

Как работает вставка в конец

Операция:

list.add(value);

В обычном случае:

1. Элемент записывается в следующий свободный индекс.

2. Копирование данных не требуется.

Сложность:

• O(1)

Когда сложность становится O(n)

Если внутренний массив заполнен:

1. Создается новый массив большего размера.

2. Все элементы копируются.

3. Старый массив освобождается GC.

// упрощенно
newCapacity = oldCapacity * 1.5

Копирование:

• O(n)

Почему в среднем это O(1)

Расширение:

1. Происходит не при каждой вставке.

2. Стоимость копирования «размазывается» по множеству операций.

Это и называется:

• амортизированной сложностью O(1)

Краткий вывод

Вставка в конец ArrayList имеет амортизированную сложность O(1), но отдельные операции могут временно стоить O(n) из-за расширения массива.