Substring Search Patterns in DSA Python - 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.

def substring_search(text: str, pattern: str) -> int:
    for i in range(len(text) - len(pattern) + 1):
        match = True
        for j in range(len(pattern)):
            if text[i + j] != pattern[j]:
                match = False
                break
        if match:
            return i
    return -1

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: Checking each character of the pattern against the text.
• How many times: For each possible start in the text, it checks up to the length of the pattern.

How Execution Grows With Input

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

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

Pattern observation: The work grows roughly by n times m, so doubling text or pattern length roughly doubles the work.

Final Time Complexity

Time Complexity: O(n * m)

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

Common Mistake

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

[OK] Correct: Because for each position in the text, we may need to check every character of the pattern, so pattern length matters too.

Interview Connect

Understanding this helps you explain why simple substring search can be slow and why smarter methods exist.

Self-Check

"What if we used a smarter algorithm like KMP? How would the time complexity change?"