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

Времевата сложност при добавяне на елемент в края на масив от тип ArrayList средно е O(1) — амортизирано константно време.

Това се случва, защото ArrayList съхранява елементите в масив с фиксиран размер. Когато добавяме елемент и има свободно място в масива, елементът просто се поставя в следващата клетка.

Ако обаче масивът е пълен, се извършва операция по разширяване — създава се нов масив с по-голям размер и всички елементи се копират в него. Тази операция отнема O(n) време, където n е броят на елементите.

Пример:

ArrayList<Integer> list = new ArrayList<>();
list.add(1); // O(1)
list.add(2); // O(1)
// При достигане на капацитета на масива се извършва разширяване — O(n)

Така, средната сложност на добавяне е — O(1), но в най-лошия случай — O(n).