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

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