Substring Search Patterns in DSA C - Time & Space Complexity

Time Complexity: Substring Search Patterns

O(n * m)

Understanding Time Complexity

We want to understand how long it takes to find a smaller string inside a bigger string.

How does the time needed grow when the strings get longer?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

This code looks for the first place where the pattern appears inside the text.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The outer loop runs from start to end of text minus pattern length.
• Nested operation: The inner while loop compares characters of pattern and text one by one.
• How many times: Outer loop runs about n - m + 1 times; inner loop runs up to m times per outer loop.

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: The work grows roughly by the product of text length and pattern length.

Final Time Complexity

Time Complexity: O(n * m)

This means the time needed 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: Because each position in the text may require checking many characters of the pattern, so pattern length matters too.

Interview Connect

Understanding how substring search time grows helps you explain and improve searching methods in real problems.

Self-Check

"What if we used a smarter algorithm like KMP that avoids re-checking characters? How would the time complexity change?"