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

Computer Science Engineering (CSE)
Design and Analysis of Algorithms
Rabin Karp algorithm and naive pattern s...

Q.	Rabin Karp algorithm and naive pattern searching algorithm have the same worst case time complexity.
A.	true
B.	false
Answer» A. true
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.

View all MCQs in: Design and Analysis of Algorithms

Discussion

Related Questions

What is the worst case time complexity of KMP algorithm for pattern searching (m = length of text, n = length of pattern)?
Worst case is the worst case time complexity of Prim’s algorithm if adjacency matrix is used?
What is the time complexity of Z algorithm for pattern searching (m = length of text, n = length of pattern)?
The naive pattern searching algorithm is an in place algorithm.
What is the auxiliary space complexity of Z algorithm for pattern searching (m = length of text, n = length of pattern)?
What is the worst case time complexity of a quick sort algorithm?
What is the worst case time complexity of dynamic programming solution of set partition problem(sum=sum of set elements)?
What is the worst case complexity of quick hull?
Is Coppersmith-Winograd algorithm better than Strassen’s algorithm in terms of time complexity?
Which of the following sorting algorithm has best case time complexity of O(n2)?