Wat is de tijdcomplexiteit van de operatie om elementen aan het begin of in het midden van een dynamische array in te voegen?

De tijdscomplexiteit van de operatie om een element aan het begin of in het midden van een dynamische array in te voegen, bedraagt gewoonlijk O(n), waarbij n het aantal elementen in de array is.

Dit komt doordat na het invoegen alle volgende elementen één positie naar rechts moeten worden verschoven om ruimte te maken voor het nieuwe element. In het ergste geval, bij het invoegen aan het begin, worden alle elementen verschoven.

Voorbeeld in Go:

package main

import "fmt"

func insertAt(slice []int, index int, value int) []int {
    slice = append(slice, 0)           // vergroot de slice
    copy(slice[index+1:], slice[index:]) // verschuif de elementen
    slice[index] = value               // voeg de waarde toe
    return slice
}

func main() {
    s := []int{1, 2, 3, 4}
    s = insertAt(s, 1, 99) // voeg 99 toe op positie 1
    fmt.Println(s)        // [1 99 2 3 4]
}