1. Computer Science Engineering (CSE)
  2. Design and Analysis of Algorithms
  3. What is the worst case time complexity o...

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 year 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