Изменения

Оценим теперь количество итераций первого вложенного цикла <tex>\mathrm{while}</tex>. Для этого рассмотрим второй вложенный цикл <tex>\mathrm{while}</tex> {{---}} он при каждом своём запуске выводит некоторое количество <tex>r \geqslant 1</tex> копий одной и той же простой строки некоторой длины <tex>p = j - k</tex>. Заметим, что строка <tex>s_2</tex> является предпростой, причём её простые строки имеют длину как раз <tex>p</tex>, т.е. её длина не превосходит <tex>r \cdot p + p - 1</tex>. Поскольку длина строки <tex>s_2</tex> равна <tex>j - i</tex>, а указатель <tex>j</tex> увеличивается по единице на единицу на каждой итерации первого вложенного цикла <tex>\mathrm{while}</tex>, то этот цикл выполнит не более <tex>r \cdot p + p - 2</tex> итераций. Худшим случаем является случай <tex>r = 1</tex>, и мы получаем, что первый вложенный цикл <tex>\mathrm{while}</tex> всякий раз выполняет не более <tex>2p - 2</tex> итераций. Вспоминая, что всего выводится <tex>n</tex> символов, получаем, что для вывода <tex>n</tex> символов требуется не более <tex>2n - 2</tex> итераций первого вложенного <tex>\mathrm{while}</tex>.