Q.

What is the worst case time complexity of KMP algorithm for pattern searching (m = length of text, n = length of pattern)?

A. o(n)
B. o(n*m)
C. o(m)
D. o(log n)
Answer» C. o(m)
Explanation: kmp algorithm is an efficient pattern searching algorithm. it has a time complexity of o(m) where m is the length of text.
1.2k
1
Do you find this helpful?
8

View all MCQs in

Design and Analysis of Algorithms

Discussion

M

mdavi
2 years ago

It is O(m+n) actually. Here is a nice little explanation https://www.w3spot.com/2020/07/kmp-algorithm-explained-in-plain-english.html
0

Related MCQs