Dinamik bir dizinin başına veya ortasına öğeler ekleme işleminin zaman karmaşıklığı nedir?

Dinamik bir dizinin başlangıcına veya ortasına bir öğe ekleme işleminin zaman karmaşıklığı genellikle O(n) olup, burada n dizideki öğe sayısıdır.

Bu, eklemeden sonra tüm sonraki öğelerin sağa doğru bir konum kaydırılması gerektiği anlamına gelir, böylece yeni öğe için yer açılır. En kötü durumda, başlangıca ekleme yapıldığında, tüm öğeler kaydırılır.

Go dilinde örnek:

package main

import "fmt"

func insertAt(slice []int, index int, value int) []int {
    slice = append(slice, 0)           // dilimi büyütüyoruz
    copy(slice[index+1:], slice[index:]) // öğeleri kaydırıyoruz
    slice[index] = value               // değeri ekliyoruz
    return slice
}

func main() {
    s := []int{1, 2, 3, 4}
    s = insertAt(s, 1, 99) // 99'u konum 1'e ekle
    fmt.Println(s)        // [1 99 2 3 4]
}