📢 Too many exams? Don’t know which one suits you best? Book Your Free Expert 👉 call Now!
  • google app store apple app store
    • ✖

      Question

      The Naive Pattern Searching algorithm has a worst-case time complexity of O(M

      • N , where 'M' is the length of the pattern and 'N' is the length of the text. This occurs when:
      A The pattern is very short. Correct Answer Incorrect Answer
      B The pattern is very long. Correct Answer Incorrect Answer
      C All characters in the text and pattern are distinct. Correct Answer Incorrect Answer
      D Many characters match before a mismatch, but the pattern shifts only by one. Correct Answer Incorrect Answer
      E The pattern is not found in the text. Correct Answer Incorrect Answer

      Solution

      The worst case for the Naive algorithm happens when the pattern almost matches at every possible shift, but a mismatch occurs at the last character. For example, searching for AAAAAB in AAAAAAAAAB. In such cases, the algorithm performs nearly M comparisons for almost every N-M+1 possible shifts, leading to O(MN) complexity.

      Practice Next
      More IT Operating System Questions
      ask-question