Algorithm Complexity | MCQs

Explanation

• The pre-processing time of Rabin and Karp Algorithm is Theta(m).
• The for loop in the pre-processing algorithm runs for m (the length of the pattern) times, hence the pre-processing time is Theta(m).
• This is the time complexity of the pre-processing phase of the Karp-Rabin algorithm.