Jaka jest złożoność czasowa operacji wstawiania elementów na początku lub w środku dynamicznej tablicy?

Złożoność czasowa operacji wstawiania elementu na początku lub w środku dynamicznej tablicy zazwyczaj wynosi O(n), gdzie n to liczba elementów w tablicy.

Dzieje się tak, ponieważ po wstawieniu konieczne jest przesunięcie wszystkich kolejnych elementów o jedną pozycję w prawo, aby zrobić miejsce dla nowego elementu. W najgorszym przypadku, przy wstawianiu na początku, przesuwają się wszystkie elementy.

Przykład w Go:

package main

import "fmt"

func insertAt(slice []int, index int, value int) []int {
    slice = append(slice, 0)           // powiększamy slice
    copy(slice[index+1:], slice[index:]) // przesuwamy elementy
    slice[index] = value               // wstawiamy wartość
    return slice
}

func main() {
    s := []int{1, 2, 3, 4}
    s = insertAt(s, 1, 99) // wstawienie 99 na pozycję 1
    fmt.Println(s)        // [1 99 2 3 4]
}