Какую временную сложность имеет операция вставки нового элемента в массив?

Вставка нового элемента в массив имеет временную сложность O(n) в худшем случае, где n — количество элементов в массиве.

Причина в том, что массив имеет фиксированный размер, и чтобы вставить элемент в середину или начало, нужно сдвинуть все последующие элементы на одну позицию вправо. Если вставка происходит в конец и есть свободное место, операция может быть O(1).

Пример:

• Вставка в конец при наличии места: O(1)
• Вставка в начало или середину: O(n) из-за сдвига элементов

В динамических массивах (например, ArrayList в Java) при переполнении массива происходит копирование в новый массив большего размера, что тоже требует O(n) времени.