What is the best & worst time complexity Of KMP algorithm

Question

Need clarification on the best time complexity & the worst time complexity of KMP algorithm. The thing that is confusing to me is the worst search time complexity of O(n). What I understood after reading online is that there are two indexes. One index i is for text & another index j is for pattern. And we don't decrement text index i. But we do decrement pattern index j when there is a mismatch & j value is greater than 0. In that case, i remains same. So how can worst time complexity is O(n)? It should be more than that like O(mn). For a specific value of i, we can have multiple iterations of j.

Also what is the best case scenario? Is it different than the worst case scenario? I am looking for an explanation in simple terms as I have already gone through different tutorials.

Answer 1

David's answer is right. You need to match j first. Then j value will be incremented & become greater than zero. After that you can decrement j value. When you increment j, you are incrementing i also. So if you decrement j index n times, that means you have already at least incremented j index n times & which in turn means you have already incremented i index n times. So you have finished traversing the text.

So time complexity would be n negative steps + n positive steps = 2n steps. And that is O(n).

You can check this link http://www.w3spot.com/2020/07/kmp-algorithm-explained-in-plain-english.html which explains it step by step with a couple of examples, one with repetitive pattern & one with non-repetitive pattern. And it is simple enough to understand.

Answer 2

KMP never increments j without incrementing i. Hence even though there can be Theta(m) decrements of j between each increment of i, the total number of decrements of j over the course of the algorithm cannot exceed the total number of increments of j, which is equal to the number of increments of i. All are Theta(n), the worst- and best-case asymptotic running time of KMP (assuming that we're finding all matches; if not then obviously the best case is Theta(m)).

Answer 3

Suppose we are searching string p in string s, the length for each is m and n.

Best case example, obviously O(m)

But if p isn't in s, the best case should be, p shifts right as long as possible once mismatched, the searching stage costs O(n + n/m).

The worst-case example, p shifts right very conservative once mismatched, the searching stage costs O(n + (m-1) * (n/m)).

Where the n/m is how many mismatches will be.

And, plus the preprocessing stage, the total time costs still O(m+n) in both best and worst cases.