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.
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.