Какие знаешь случаи, когда сложность добавления элемента в конец ArrayList равна O(n)

В большинстве случаев добавление элемента в конец ArrayList имеет сложность O(1), но есть исключения:

1. При заполнении внутреннего массива – когда capacity достигнут, создается новый массив (обычно в 1.5-2 раза больше), все элементы копируются в него, затем добавляется новый элемент. Это O(n).

ArrayList<Integer> list = new ArrayList<>(2); // capacity = 2
list.add(1); // O(1)
list.add(2); // O(1)
list.add(3); // O(n) – требуется resize массива

2. При использовании ensureCapacity() – если явно увеличиваем capacity, происходит копирование массива.

ArrayList<String> list = new ArrayList<>();
list.ensureCapacity(1000); // O(n) если текущий size > 0