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

Вставка элемента в центральную часть массива требует сдвига всех элементов, стоящих после позиции вставки, чтобы освободить место для нового элемента.

Если длина массива — n, то в худшем случае нужно сдвинуть примерно n/2 элементов. Операция сдвига — это копирование элементов, что занимает время, пропорциональное количеству сдвигаемых элементов.

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

Пример на Java:

int[] arr = new int[10];
// вставляем элемент в позицию pos
int pos = 5;
int newValue = 42;
// сдвигаем элементы вправо
for (int i = arr.length - 1; i > pos; i--) {
    arr[i] = arr[i - 1];
}
arr[pos] = newValue;

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