Временная сложность операции вставки элемента в начало или в середину динамического массива обычно составляет O(n), где n — количество элементов в массиве.

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

Пример на Go:

package main

import "fmt"

func insertAt(slice []int, index int, value int) []int {
    slice = append(slice, 0)           // увеличиваем срез
    copy(slice[index+1:], slice[index:]) // сдвигаем элементы
    slice[index] = value               // вставляем значение
    return slice
}

func main() {
    s := []int{1, 2, 3, 4}
    s = insertAt(s, 1, 99) // вставка 99 на позицию 1
    fmt.Println(s)        // [1 99 2 3 4]
}

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