Изменения

На каждой стадии <tex>s</tex> из <tex>\log m</tex> стадий анализа образца цикл <tex>for</tex> производит <tex>2^{s-1}</tex> итераций <tex>(2^{s-1} \leqslant i \leqslant 2^{s}-1)</tex>. Если не считать время работы процедур <tex>merge</tex> и <tex>extend</tex>, каждая итерация требует фиксированного времени. Для всех итераций на шаге <tex>s</tex> процедуре <tex>extend</tex> требуется время <tex>O(m)</tex>. Ранее было показано, что время работы <tex>merge</tex> пропорционально числу искомых несовпадений. Таким образом, каждый вызов <tex>merge</tex> занимает время <tex>O(min\{2^{log(m)-s}4k+1, m-2^{s}\})</tex>, что равно <tex>O(2k2^{\log (m-s)})</tex>. Таким образом, общее время для стадии <tex>s</tex> равно <tex>O(m+2^{l-1}(2k2^{\log (m-s)}))</tex> = <tex>O(km)</tex>. Проведя суммирование по всем стадиям, получаем общее время счета <tex>O(\sum_{i=1}^{\log m} km)</tex> = <tex>O(km \log m)</todo)tex>. Таким образом, общие затраты времени, включающие предварительную обработку образца и анализ текста, равны <tex>O(k(n + m \log m))</tex>.