Care este complexitatea temporală a operației de inserare a elementelor la începutul sau în mijlocul unui array dinamic?

Complexitatea temporară a operației de inserare a unui element la începutul sau în mijlocul unui array dinamic este de obicei O(n), unde n reprezintă numărul de elemente din array.

Aceasta se datorează faptului că, după inserare, toate elementele următoare trebuie mutate cu o poziție spre dreapta pentru a face loc pentru noul element. În cel mai rău caz, la inserarea la început, toate elementele sunt mutate.

Exemplu în Go:

package main

import "fmt"

func insertAt(slice []int, index int, value int) []int {
    slice = append(slice, 0)           // mărim slice-ul
    copy(slice[index+1:], slice[index:]) // mutăm elementele
    slice[index] = value               // inserăm valoarea
    return slice
}

func main() {
    s := []int{1, 2, 3, 4}
    s = insertAt(s, 1, 99) // inserare 99 la poziția 1
    fmt.Println(s)        // [1 99 2 3 4]
}