Mekkora az időbeli komplexitása az elemek beszúrásának a dinamikus tömb elejére vagy közepére?

A dinamikus tömb elejére vagy közepére történő elem beszúrásának időkomplexitása általában O(n), ahol n a tömbben lévő elemek száma.

Ez azért van, mert a beszúrás után minden következő elemet egy pozícióval jobbra kell mozgatni, hogy helyet csináljunk az új elemnek. A legrosszabb esetben, amikor a kezdőbe szúrunk be, minden elem elmozdul.

Példa Go nyelven:

package main

import "fmt"

func insertAt(slice []int, index int, value int) []int {
    slice = append(slice, 0)           // növeljük a szelet
    copy(slice[index+1:], slice[index:]) // elemek mozgatása
    slice[index] = value               // érték beszúrása
    return slice
}

func main() {
    s := []int{1, 2, 3, 4}
    s = insertAt(s, 1, 99) // 99 beszúrása a 1. pozícióba
    fmt.Println(s)        // [1 99 2 3 4]
}