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

Временная сложность добавления элемента в конец массива зависит от реализации массива:

• Если массив имеет заранее выделённый буфер с запасом (динамический массив, например, ArrayList в Java), то добавление обычно происходит за амортизированное O(1) — элемент просто помещается в следующую свободную ячейку.

• Если буфер заполнен, происходит операция расширения массива: выделяется новый массив большего размера, копируются все элементы, затем добавляется новый элемент. Эта операция занимает O(n) времени, где n — текущий размер массива.

Таким образом, средняя (амортизированная) временная сложность добавления в конец динамического массива — O(1), но в худшем случае — O(n).