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

Time Complexity: String Pattern Matching Naive

O(n * m)

Understanding Time Complexity

We want to understand how the time needed to find a pattern in a text grows as the text and pattern get longer.

Specifically, how many steps does the naive search take when looking for a pattern inside a larger string?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

int naiveSearch(char *text, char *pattern) {
    int n = strlen(text);
    int m = strlen(pattern);
    for (int i = 0; i <= n - m; i++) {
        int j;
        for (j = 0; j < m; j++) {
            if (text[i + j] != pattern[j])
                break;
        }
        if (j == m)
            return i; // pattern found at index i
    }
    return -1; // pattern not found
}
    

This code tries to find the first place where the pattern appears in the text by checking each possible position one by one.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The nested loops comparing characters of the pattern with the text.
• How many times: The outer loop runs about (n - m + 1) times, and for each, the inner loop runs up to m times.

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), 10 (pattern)	About 91 * 10 = 910 comparisons
1000 (text), 50 (pattern)	About 951 * 50 = 47,550 comparisons

Pattern observation: Doubling the text or pattern length roughly doubles or multiplies the work, showing a growth close to the product of their sizes.

Final Time Complexity

Time Complexity: O(n * m)

This means the time to find the pattern grows roughly by multiplying the length of the text and the pattern.

Common Mistake

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

[OK] Correct: The pattern length matters too because for each position in the text, we may compare many characters of the pattern before deciding if it matches or not.

Interview Connect

Understanding this simple search helps build a foundation for more efficient algorithms and shows you can analyze how nested loops affect performance.

Self-Check

"What if we changed the pattern to be very short, like a single character? How would the time complexity change?"