Question

Rabin Karp algorithm and naive pattern searching algorithm have the same worst case time complexity.

(a) true

(b) false

I had been asked this question by my school principal while I was bunking the class.

This is a very interesting question from Searching in portion Searching of Data Structures & Algorithms II

Answer 1

Correct answer is (a) true

Best explanation: The worst case time complexity of Rabin Karp algorithm is O(m*n) but it has a linear average case time complexity. So Rabin Karp and naive pattern searching algorithm have the same worst case time complexity.