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

Что проверяют

Знаете ли вы, что за ArrayList стоит обычный массив, и умеете ли отличать амортизированную оценку от стоимости одной операции. Правильный ответ звучит как «амортизированно O(1), в худшем случае O(n) на расширении». Следом спрашивают про коэффициент роста и про вставку в середину.

Как отвечать

• добавление в конец: add(e) пишет элемент по индексу size и увеличивает счётчик, это O(1). Когда массив заполнен, вызывается grow, выделяется новый массив, Arrays.copyOf переносит содержимое, и такая операция стоит O(n);
• амортизация: рост геометрический, поэтому копирования случаются всё реже. Суммарная стоимость n вставок линейна, средняя на операцию константна. Если бы массив рос на фиксированное число ячеек, амортизированная оценка была бы O(n);
• цифры OpenJDK: newCapacity = oldCapacity + (oldCapacity >> 1), то есть в полтора раза. Пустой список хранит общий пустой массив, ёмкость 10 выделяется при первом добавлении. Верхняя граница длины около Integer.MAX_VALUE;
• вставка по индексу: add(index, e) сдвигает хвост через System.arraycopy и стоит O(n) независимо от запаса ёмкости. То же у remove(index). Чтение get(i) это O(1) всегда;
• как убрать перекопирования: конструктор с начальной ёмкостью или ensureCapacity(n), когда размер известен заранее.

Хорошо добавить сравнение: у LinkedList вставка в конец O(1) без копирований, но каждый элемент это отдельный узел с накладными расходами, обход плохо ложится в кэш процессора, и на реальных объёмах ArrayList выигрывает почти всегда. Про многопоточность: ArrayList не синхронизирован, гонка на grow приводит к потерянным элементам или ArrayIndexOutOfBoundsException.

Где спотыкаются

Отвечают просто «O(1)» и не упоминают расширение. Это ровно та деталь, ради которой вопрос и задан.

Называют рост «в два раза». У ArrayList в OpenJDK множитель полтора, вдвое растут HashMap и StringBuilder.

Путают амортизированную оценку со средней по случайным данным. Вероятности тут нет: усреднение идёт по последовательности операций, а отдельная вставка в худшем случае всё равно O(n).