Изменения

Время работы алгоритма составит <tex>O(n)</tex>. Для доказательства этого потребуется новое обозначение <tex>w_i</tex> {{---}} количество итераций цикла <tex>while</tex> на <tex>i</tex>-ом шаге. Итоговое время работы алгоритма составит <tex>\sum\limits_{i=2}^n w_i</tex>. Теперь стоит отметить, что <tex>k</tex> увеличивается на каждом шаге не более чем на единицу, значит максимально возможное значение <tex>k = n - 1.</tex>. Внутри цикла <tex>while</tex> значение <tex>k</tex> лишь уменьшается, а из предыдущего утверждения получается, что оно не может уменьшиться больше, чем <tex>n-1</tex> раз, значит <tex>\sum\limits_{i=2}^n w_i \le n</tex>, что дает итоговую оценку времени алгоритма <tex>O(n)</tex>.