Wie ist die algorithmische Komplexität beim Hinzufügen von Elementen ans Ende eines Arrays?

O(1) амортизировано (amortized).

При добавлении элемента в конец массива, если есть свободное место, происходит простое присваивание, что занимает O(1).

Если массив заполнен, требуется перевыделение памяти и копирование всех существующих элементов в новое, большее хранилище. Эта операция занимает O(N), где N - количество элементов в массиве.

Благодаря стратегии удвоения размера при перевыделении, средняя стоимость добавления элемента за большое количество операций стремится к постоянной величине.

Пример на Swift:

var array = [Int]()

// Добавление, скорее всего O(1)
array.append(1)

// Может потребовать перевыделения памяти и стать O(N)
// Но амортизированная стоимость для всей последовательности append остаётся O(1)
array.append(2)