ЁЯУв Too many exams? DonтАЩt know which one suits you best? Book Your Free Expert ЁЯСЙ call Now!
  • google app store apple app store
    • тЬЦ

      Question

      What is the time complexity of the KMP algorithm for

      searching a pattern of length 'M' in a text of length 'N'?
      A O(MN) Correct Answer Incorrect Answer
      B O(N log M) Correct Answer Incorrect Answer
      C O(N + M) Correct Answer Incorrect Answer
      D O(M^2) Correct Answer Incorrect Answer
      E O(N^2) Correct Answer Incorrect Answer

      Solution

      The KMP algorithm has a time complexity of O(M) for preprocessing the pattern (building the LPS array) and O(N) for searching the text. Therefore, the total time complexity is O(N + M), which is significantly better than the Naive algorithm's worst-case O(MN).

      Practice Next
      More IT Operating System Questions
      ask-question