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

Времевата сложност на операцията за вмъкване на елемент в началото или в средата на динамичен масив обикновено е 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]
}