Какая будет сложность операции вставки в середину ArrayList

Вставка в середину ArrayList имеет временную сложность O(n). Причина: при вставке элемента все последующие элементы нужно сдвинуть на одну позицию вправо. В худшем случае (вставка в начало) потребуется сдвинуть все n элементов. Пример: ```java ArrayList list = new ArrayList<>(Arrays.asList(1, 2, 3, 4)); list.add(2, 99); // Вставка по индексу 2 // Теперь list = [1, 2, 99, 3, 4] ``` В этом примере элементы 3 и 4 сдвигаются вправо. Если ArrayList заполнен, может потребоваться увеличение capacity (O(n)), но амортизированно это O(1). Основные затраты - именно на сдвиг элементов.