Qual é a complexidade temporal da operação de inserir elementos no início ou no meio de um array dinâmico?

A complexidade temporal da operação de inserção de um elemento no início ou no meio de um array dinâmico geralmente é O(n), onde n é o número de elementos no array.

Isto deve-se ao facto de, após a inserção, ser necessário deslocar todos os elementos seguintes uma posição para a direita para abrir espaço para o novo elemento. No pior caso, ao inserir no início, todos os elementos são deslocados.

Exemplo em Go:

package main

import "fmt"

func insertAt(slice []int, index int, value int) []int {
    slice = append(slice, 0)           // aumentamos o slice
    copy(slice[index+1:], slice[index:]) // deslocamos os elementos
    slice[index] = value               // inserimos o valor
    return slice
}

func main() {
    s := []int{1, 2, 3, 4}
    s = insertAt(s, 1, 99) // inserção de 99 na posição 1
    fmt.Println(s)        // [1 99 2 3 4]
}