Aká je časová zložitosť operácie vloženia prvkov na začiatok alebo do stredu dynamického poľa?

Časová zložitosť operácie vloženia prvku na začiatok alebo do stredu dynamického poľa je zvyčajne O(n), kde n je počet prvkov v poli.

To je spôsobené tým, že po vložení je potrebné posunúť všetky nasledujúce prvky o jednu pozíciu doprava, aby sa uvoľnilo miesto pre nový prvok. V najhoršom prípade, pri vkladaní na začiatok, sa posunú všetky prvky.

Príklad v Go:

package main

import "fmt"

func insertAt(slice []int, index int, value int) []int {
    slice = append(slice, 0)           // zväčšíme rez
    copy(slice[index+1:], slice[index:]) // posunieme prvky
    slice[index] = value               // vložíme hodnotu
    return slice
}

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