Какая временная сложность у операции вставки элемента в среднюю часть массива, реализованного через ArrayList?

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