Когда операция вставки элемента в массив приводит к времени выполнения, пропорциональному размеру массива?

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

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