В каких ситуациях добавление элемента в конец ArrayList может иметь временную сложность O(n)?

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

При добавлении нового элемента:

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

Таким образом, добавление элемента может иметь временную сложность O(n) именно в момент расширения внутреннего массива.