📢 Too many exams? Don’t know which one suits you best? Book Your Free Expert 👉 call Now!

    Question

    The Naive Pattern Searching algorithm has a worst-case

    time complexity of O(MN), 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