Jaká je časová složitost operace vložení prvků na začátek nebo do středu dynamického pole?

Časová složitost operace vložení prvku na začátek nebo do středu dynamického pole je obvykle O(n), kde n je počet prvků v poli.

To je způsobeno tím, že po vložení je třeba posunout všechny následující prvky o jednu pozici doprava, aby se uvolnilo místo pro nový prvek. V nejhorším případě, při vkládání na začátek, jsou všechny prvky posunuty.

Příklad v Go:

package main

import "fmt"

func insertAt(slice []int, index int, value int) []int {
    slice = append(slice, 0)           // zvětšíme řez
    copy(slice[index+1:], slice[index:]) // posuneme prvky
    slice[index] = value               // vložíme hodnotu
    return slice
}

func main() {
    s := []int{1, 2, 3, 4}
    s = insertAt(s, 1, 99) // vložení 99 na pozici 1
    fmt.Println(s)        // [1 99 2 3 4]
}