Какова асимптотическая сложность вставки элемента в начало или середину `slice` в Go?

Вставка элемента в начало или середину slice всегда имеет сложность O(n).

Это связано с тем, что для освобождения места под новый элемент необходимо сдвинуть все последующие элементы на одну позицию вправо. Эта операция сдвига занимает линейное время, пропорциональное количеству сдвигаемых элементов.

Операция может также вызвать реаллокацию (копирование всего слайса в новый массив), если capacity недостаточно, что также является операцией O(n).

Пример реализации вставки:

func insert(slice []int, index int, value int) []int {
    // Шаг 1: Увеличиваем слайс на один элемент.
    // Это может вызвать реаллокацию O(n), если cap == len.
    slice = append(slice, 0) // Значение не важно, оно будет перезаписано

    // Шаг 2: Сдвигаем элементы вправо от индекса вставки.
    // Это операция копирования, сложность O(n - index).
    copy(slice[index+1:], slice[index:])

    // Шаг 3: Вставляем новый элемент на освободившееся место.
    slice[index] = value

    return slice
}

Таким образом, в отличие от добавления в конец (амортизированная O(1)), вставка в произвольное место является дорогой операцией.