The average case and best case complexity of Rabin-Karp algorithm is O(m + n) and the worst case complexity is O(mn).
Points to remember
The worst-case complexity occurs when spurious hits occur a number for all the windows. A spurious hit is when the hash of a window is the same as the pattern but the actual text does not match.
We need to choose a multiplier and a modulus . We choose 26 in this case since we are working only with lower case english alphabets in the following example. The modulus is a large prime number so that we avoid collisions. We can choose 1001 in this case.
We need to calculate the potential match in the text’s hash per window. Hence we need to subtract the hash value of the older character and add the hash value of the newer character suitably.
