Qual è la complessità temporale dell'operazione di inserimento di elementi all'inizio o nel mezzo di un array dinamico?

La complessità temporale dell'operazione di inserimento di un elemento all'inizio o a metà di un array dinamico è generalmente O(n), dove n è il numero di elementi nell'array.

Ciò è dovuto al fatto che, dopo l'inserimento, tutti gli elementi successivi devono essere spostati di una posizione verso destra per fare spazio al nuovo elemento. Nel peggiore dei casi, inserendo all'inizio, tutti gli elementi vengono spostati.

Esempio in Go:

package main

import "fmt"

func insertAt(slice []int, index int, value int) []int {
    slice = append(slice, 0)           // aumentiamo la capacità del slice
    copy(slice[index+1:], slice[index:]) // spostiamo gli elementi
    slice[index] = value               // inseriamo il valore
    return slice
}

func main() {
    s := []int{1, 2, 3, 4}
    s = insertAt(s, 1, 99) // inserimento di 99 alla posizione 1
    fmt.Println(s)        // [1 99 2 3 4]
}