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

Вставка элемента в начало динамического массива (например, ArrayList в Java) имеет временную сложность O(n), где n — количество элементов в массиве.

Это связано с тем, что при вставке в начало все существующие элементы нужно сдвинуть на одну позицию вправо, чтобы освободить место для нового элемента. Сам процесс копирования элементов занимает линейное время.

Пример:

ArrayList<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);

// Вставка в начало
list.add(0, 0); // сдвигает все элементы вправо

Таким образом, вставка в конец обычно быстрее (амортизированное O(1)), а в начало — O(n).