Изменения

Внешний цикл <tex>\mathrm{while}</tex> делает не более <tex>n</tex> итераций, поскольку в конце каждой его итерации к результату добавляется <tex> i </tex> увеличивается как минимум один символ (а всего символов на <tex> 1 </tex>. Второй внутренний цикл выполнится суммарно не более <tex>n</tex>), так он добавляет к ответу все символы, причём каждый символ лишь единожды.

Оценим теперь количество итераций первого вложенного цикла <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>. Следовательно, алгоритм Дюваля выполняется за <tex>O(n)</tex>.

Легко оценить и число сравнений символовИтого получаем, выполняемых алгоритмом Дювалячто итоговая асимптотика алгоритма составляет <tex> O(n) </tex>. Поскольку каждая итерация первого вложенного цикла  Отметим, что алгоритму требуется <tex>\mathrm{while}O(1) </tex> производит два сравнения символов, а также одно сравнение производится после последней итерации цикла, то общее число сравнений символов не превосходит памяти: на указатели <tex>4n - 3i, j, k </tex>.