CODEWITHSUNDEEP
algorithmknuth-morris-pratt
Ansari
Ansari

Reputation: 1935

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

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

Upvotes: 0

Views: 3243

Answers (2)

alestanis
alestanis

Reputation: 21863

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

Upvotes: 4

davepmiller
davepmiller

Reputation: 2708

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

Upvotes: 1

Related Questions