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

Времевата сложност при добавяне на елемент към ArrayList обикновено е амортизирана до O(1). Това се дължи на факта, че:

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

Обаче, разширението не се случва при всяко добавяне, а периодично, така че средната (амортизирана) сложност на добавяне остава O(1).

Пример:

ArrayList<Integer> list = new ArrayList<>();
list.add(10); // Амортизирано O(1)