Hogyan értékeljük az ArrayList-hez való elem hozzáadásának időbeli összetettségét?

Временная сложность операции добавления элемента в ArrayList обычно амортизированно O(1). Это связано с тем, что при добавлении элемента в конец списка, если внутренний массив имеет свободное место, элемент просто помещается в следующую ячейку.

Однако, если внутренний массив заполнен, происходит его расширение (копирование элементов в новый массив большего размера), что занимает O(n) времени, где n — текущий размер списка.

Таким образом:

• В среднем (амортизированно) добавление — O(1)
• В худшем случае (при расширении массива) — O(n)

Пример:

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