String Pattern Matching Naive in DSA Python - Time & Space Complexity

Time Complexity: String Pattern Matching Naive

O(n * m)

Understanding Time Complexity

We want to understand how long it takes to find a pattern inside a text using a simple method.

How does the time needed grow when the text or pattern gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

def naive_pattern_search(text: str, pattern: str) -> int:
    n = len(text)
    m = len(pattern)
    for i in range(n - m + 1):
        j = 0
        while j < m and text[i + j] == pattern[j]:
            j += 1
        if j == m:
            return i
    return -1

This code checks every possible place in the text to see if the pattern matches starting there.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Comparing characters of the pattern with the text one by one.
• How many times: For each position in the text (up to n - m + 1), it may compare up to m characters.

How Execution Grows With Input

As the text and pattern get longer, the number of comparisons grows roughly by multiplying their lengths.

Input Size (n)	Approx. Operations
10 (text), 3 (pattern)	About 8 * 3 = 24 comparisons
100 (text), 5 (pattern)	About 96 * 5 = 480 comparisons
1000 (text), 10 (pattern)	About 991 * 10 = 9,910 comparisons

Pattern observation: Doubling the text or pattern length roughly doubles the work, so the total work grows like the product of their sizes.

Final Time Complexity

Time Complexity: O(n * m)

This means the time needed grows proportionally to the length of the text times the length of the pattern.

Common Mistake

[X] Wrong: "The search always takes time proportional to the text length only."

[OK] Correct: Because for each position in the text, the pattern characters are also checked one by one, so pattern length matters too.

Interview Connect

Understanding this simple search helps build intuition for more advanced methods and shows you can analyze nested loops clearly.

Self-Check

"What if we stopped searching after the first mismatch instead of checking all characters? How would the time complexity change?"