Koja je vremenska složenost operacije umetanja elemenata na početak ili u sredinu dinamičkog niza?

Vremenska složenost operacije umetanja elementa na početak ili u sredinu dinamičkog niza obično je O(n), gde je n broj elemenata u nizu.

To je zato što nakon umetanja, svi sledeći elementi moraju biti pomereni za jednu poziciju udesno da bi se napravilo mesto za novi element. U najgorem slučaju, pri umetanju na početak, pomeraju se svi elementi.

Primer u Go:

package main

import "fmt"

func insertAt(slice []int, index int, value int) []int {
    slice = append(slice, 0)           // povećavamo rez
    copy(slice[index+1:], slice[index:]) // pomeramo elemente
    slice[index] = value               // umetnemo vrednost
    return slice
}

func main() {
    s := []int{1, 2, 3, 4}
    s = insertAt(s, 1, 99) // umetanje 99 na poziciju 1
    fmt.Println(s)        // [1 99 2 3 4]
}