Чем обусловлена временная сложность O(n) при добавлении элемента в ArrayList в худшем случае?

Худший случай добавления элемента в ArrayList в Java наступает, когда внутренний массив заполнен и требуется его расширение (resize).

Процесс расширения:

1. Создается новый массив большего размера (обычно в 1.5 раза, начиная с Java 7).
2. Все существующие элементы копируются в новый массив.
3. Копирование всех n элементов и составляет сложность O(n).

Пример:

// ArrayList с начальной вместимостью 2
ArrayList<Integer> list = new ArrayList<>(2);
list.add(1); // Вместимость 2, элементы: [1]
list.add(2); // Вместимость 2, элементы: [1, 2] - массив заполнен
list.add(3); // Требуется расширение! Создается новый массив,
             // копируются элементы [1, 2], затем добавляется 3.
             // Временная сложность операции add(3) — O(n).

Рекомендация: Если известно примерное количество элементов, задавайте начальную вместимость через конструктор ArrayList(int initialCapacity), чтобы минимизировать операции расширения.