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

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