Quand l'opération d'insertion d'un élément dans un tableau entraîne-t-elle un temps d'exécution proportionnel à la taille du tableau?

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

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