Как определить затратность по времени операции вставки нового элемента в массив?

Вставка нового элемента в массив зависит от типа массива и способа вставки:

• Для статического массива (fixed-size): вставка в конец — O(1), если есть свободное место. Вставка в середину или начало — O(n), так как нужно сдвинуть элементы.
• Для динамического массива (например, ArrayList в Java или NSMutableArray в iOS):
  • Вставка в конец обычно амортизированно O(1), но при переполнении массива происходит перераспределение памяти и копирование — O(n).
  • Вставка в середину или начало — O(n), из-за сдвига элементов.

Таким образом, затратность по времени зависит от позиции вставки и реализации массива. Обычно вставка в конец динамического массива — амортизированно быстрая, остальные вставки требуют сдвига элементов и имеют линейную сложность.