Каква е времевата сложност на операцията за добавяне на елемент към динамичен масив?

Добавянето на елемент към динамичен масив обикновено има амортизирана времева сложност O(1).

Обяснение:

• Ако в масива има свободно място, елементът се добавя за константно време.
• Ако няма място, масивът заделя нов блок памет по-голям (обикновено два пъти по-голям), копира старите елементи и добавя новия.

Въпреки че операцията по разширяване отнема O(n), тя не се случва често, затова средната (амортизирана) сложност на добавяне остава O(1).

Пример на Go с използване на срезове:

var arr []int
arr = append(arr, 10) // добавяне на елемент

append автоматично ще разшири среза при необходимост.