Почему ArrayList.remove(i) в цикле ведёт к квадратичному времени выполнения?

На вопрос удаление каждого К-того элемента из arraylist по кругу был предложен ответ
import java.util.ArrayList;
public class MyClass { public static void main(String[] args) { ArrayList list1 = new ArrayList(); int n = 10; int k = 3; for (int i = 0; iЭто квадратичный алгоритм O(n²), но по-видимому это не очевидно, так как приводит к вопросам:
... где вы тут n^2 увидели? ... тут один цикл while, который за каждую итерацию "убирает" по одному элементу, где здесь квадрат?
Как себя ведут популярные реализации Java? Гарантирует ли спецификация языка O(n) поведение для ArrayList.remove(i) для произвольного индекса?

Ответ

Из Java API Specification по поводу ArrayList
Операции size, isEmpty, get, set, iterator и listIterator выполняются за константное время. Операция add выполняется за амортизированное время O(1), то есть n элементов будут добавлены за O(n). Все прочие операции выполняются за линейное время (грубо говоря).
The size, isEmpty, get, set, iterator, and listIterator operations run in constant time. The add operation runs in amortized constant time, that is, adding n elements requires O(n) time. All of the other operations run in linear time (roughly speaking).
ArrayList.remove() относится к категории "прочие операции", поэтому удаление одного произвольного элемента это O(n) операция. Цикл из вопроса по одному удаляет элементы (всего n удалений). Итого: n * O(n) = O(n * n) то есть представленный в вопросе алгоритм является квадратичным.