Изменения
Нет описания правки
Теперь рассмотрим произвольную итерацию внешнего цикла <tex>for</tex>. Возможно одно из трёх:
# <tex>s[i] = s[k]</tex>. Тогда значение <tex>k</tex> увеличивается на 1, цикл <tex>while</tex> не итерируется
# <tex>k = 0 </tex> <tex>\& </tex> <tex>s[i] \ne s[k]</tex>. Тогда значение <tex>k</tex> не изменяется, цикл <tex>while</tex> не итерируется
# <tex>while</tex> итерируется хотя бы раз. При каждой итерации <tex>while</tex> значение <tex>k</tex> может, очевидно, лишь уменьшаться, при этом, в силу отмеченного выше очевидного наблюдения, общее число итераций <tex>while</tex> для всех итераций <tex>for</tex> не превышает <tex>n</tex>
Таким образом, общее время работы - <tex>O(n)</tex>.
