Почему вложенный while не всегда даёт O(n²)

Условие

В алгоритме скользящего окна внешний цикл двигает right от 0 до n−1, а внутренний while только увеличивает left, никогда не сбрасывая его назад. Почему сложность может быть O(n)?

Ответ

Оба указателя суммарно делают не более n сдвигов каждый. Стоимость внутреннего цикла распределена по всему проходу, а не повторяется n раз для каждого right.

Линейная оценка предполагает O(1) работу на один сдвиг, например обновление счётчика. Если внутри заново копируется окно или пересчитывается его сумма, сложность может снова стать квадратичной. Считайте общее число операций, а не только визуальную глубину вложенности циклов.