Can someone explain to me the Rabin-Karp algorithm's complexity?

Question

I'm trying to understand why the worst case running time of the Rabin-Karp algorithm is O(nm) and the average case is O(n+m).

Can someone help me with that?

Answer 1

Wiki explains about the time complexity of the algorithm pretty well.

It can be said that the effectiveness (read it as ability to dynamically reuse already calculated hash value in constant time) of the hash computation function is a deciding factor during the calculation of time complexity of the algorithm.

Let us see how the hash computation makes this difference.

---

Time complexity is O(nm) for cases when :

call hash(s[1..m])                  // O(m) additive
for index from 1 to n-m+1           // O(n)
    //Code to check if substring matches
    call hash(s[index+1..index+m])  // Inefficient hash function, takes O(m), just like naive string matching

Compared to O(nm), additive O(m) is largely ignored.

Giving, O(m) + O(n)*O(m) = O(nm)

---

Time complexity is O(n+m) for cases when :

call hash(s[1..m])                  // O(m) additive
for index from 1 to n-m+1           // O(n)
    //Code to check if substring matches
    call hash(s[index+1..index+m])  //Efficient hash function which takes only O(1), applies Rolling Hashing

Giving, O(m) + O(n)*O(1) = O(m) + O(n) = O(m+n)