In many applications,we expect few valid shifts-perhaps some constant c of them.In such applications,the expected matching time of the algorithm is only O((n-m +1)+cm)=O(n +m),plus the time required to process spurious hits.We can base a heuristic analysis on the assumption that reducing values mod- ulo acts like a random mapping fromto We can then expect that the number of spurious hits is O(n/q),since we can es- timate the chance that an arbitrary ts will be equivalent to p,modulo q,as 1/q. Since there are O(n)positions at which the test of line 10 fails and we spend O(m) time for each hit,the expected matching time taken by the Rabin-Karp algorithm is O(n)+O(m(v+n/q)). where v is the number of valid shifts.This running time is O(n)ifv=O(1)and we choose g=m.That is,if the expected number of valid shifts is small (O(1)) and we choose the prime g to be larger than the length of the pattern,then we can expect the Rabin-Karp procedure to use only O(n m)matching time.Since m <n,this expected matching time is O(n)