¿Cuál es la complejidad temporal de la operación de insertar elementos al principio o en el medio de un array dinámico?

La complejidad temporal de la operación de insertar un elemento al principio o en medio de un array dinámico suele ser O(n), donde n es la cantidad de elementos en el array.

Esto se debe a que, después de la inserción, es necesario desplazar todos los elementos siguientes una posición hacia la derecha para hacer espacio para el nuevo elemento. En el peor de los casos, al insertar en el principio, se desplazan todos los elementos.

Ejemplo en Go:

package main

import "fmt"

func insertAt(slice []int, index int, value int) []int {
    slice = append(slice, 0)           // aumentamos el tamaño del slice
    copy(slice[index+1:], slice[index:]) // desplazamos los elementos
    slice[index] = value               // insertamos el valor
    return slice
}

func main() {
    s := []int{1, 2, 3, 4}
    s = insertAt(s, 1, 99) // inserta 99 en la posición 1
    fmt.Println(s)        // [1 99 2 3 4]
}