Изменения

Время работы алгоритма составит <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>while</tex> в итоге выполнится менее <tex>\sum\limits_{i=2}^n w_i \le n</tex>раз, что дает итоговую оценку времени алгоритма <tex>O(n)</tex>.