| 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. | |
Login to Continue
It will take less than 2 minutes
mdavi
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