Изначальный подсчёт хешей выполняется за <tex>O(m)</tex>.
Каждая итерация выполняется за <tex>O(1)</tex>, так как при удалении первого символа строки и добавлении символа в конец считать хеш новой строки при помощи хеша изначальной строки возможно за В цикле всего <tex>O(n - m + 1)</tex>:итераций.
<tex>\mathrm{hash}(s[i + 1..i + m - 1]) = (\mathrm{hash}(s[i..i + m - 1]) - p^{m - 1} s[i]) \bmod r</tex>. <tex>\mathrm{hash}(s[i + 1..i + m]) = (p \cdot \mathrm{hash}(s[i + 1..i + m - 1]) + s[i + m]) \bmod r</tex>. Получается : <tex>\mathrm{hash}(s[i + 1..i + m]) = (p \cdot \mathrm{hash}(s[i..i + m - 1]) - p^{m} s[i] + s[i + m]) \bmod r</tex>. В цикле всего <tex>n - m + 1</tex> итераций. Итоговое время работы алгоритма <tex>O(n + m)</tex>.
== Надёжность ==
