Какова временная сложность выполнения основных операций с ArrayList?

Временная сложность основных операций с ArrayList в Java:

• Доступ по индексу (get, set): O(1) — прямой доступ к элементу по индексу.

• Добавление элемента в конец (add(E e)): амортизированное O(1) — обычно добавление быстрое, но при переполнении внутреннего массива происходит копирование, что занимает O(n).

• Вставка или удаление элемента в середине списка (add(index, e), remove(index)): O(n) — из-за необходимости сдвига элементов после позиции вставки/удаления.

• Поиск элемента (indexOf, contains): O(n) — требуется перебор элементов.

Пример:

ArrayList<Integer> list = new ArrayList<>();
list.add(10); // O(1)
int val = list.get(0); // O(1)
list.add(0, 5); // O(n), сдвиг элементов
list.remove(0); // O(n), сдвиг элементов