Каква е времевата сложност на операцията по вмъкване на елемент в началото на динамичен масив 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).