What is the minimum number of comparisons under best case for KMP Algorithm?

Question

What is the minimum number of comparisons under best case scenario for KMP algorithm ?

Answer 1

Well, the minimum number of comparisons in best case would be the length of your string, meaning you found a match first try. The algorithm is O(n), meaning that the upper bound or worst case scenario would take n comparisons where n is the length of the string that you are searching. The wiki is pretty good. http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm

Answer 2

The best case happens when the string you are looking for is located just at the beginning of your text string. In this case, if you are looking for a k letter string inside a n letter string, the best case number of comparisons would be k.

You also have to take into account the overhead of computing the table, based on your k letter word, that will allow you to know which letters to skip if you don't find a match. In any case, this construction is done in O(k).