What is the time complexity of inserting elements at the beginning or middle of a dynamic array?

The time complexity of inserting an element at the beginning or middle of a dynamic array is usually O(n), where n is the number of elements in the array.

This is because, after insertion, all subsequent elements need to be shifted one position to the right to make space for the new element. In the worst case, when inserting at the beginning, all elements are shifted.

Example in Go:

package main

import "fmt"

func insertAt(slice []int, index int, value int) []int {
    slice = append(slice, 0)           // increase the slice
    copy(slice[index+1:], slice[index:]) // shift elements
    slice[index] = value               // insert the value
    return slice
}

func main() {
    s := []int{1, 2, 3, 4}
    s = insertAt(s, 1, 99) // insert 99 at position 1
    fmt.Println(s)        // [1 99 2 3 4]
}