Preg_match for pattern matching in PHP - Time & Space Complexity

Time Complexity: Preg_match for pattern matching

O(n)

Understanding Time Complexity

When using preg_match in PHP, it's important to know how the time it takes grows as the input string gets longer.

We want to understand how the pattern matching works scales with input size.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

$string = "Hello, this is a sample text.";
$pattern = '/sample/';
if (preg_match($pattern, $string)) {
    echo "Match found!";
} else {
    echo "No match.";
}
    

This code checks if the word "sample" appears anywhere in the given string.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The pattern matcher scans through the input string character by character.
• How many times: Up to once per character in the string, depending on the pattern and input.

How Execution Grows With Input

The time to check the pattern grows roughly in proportion to the length of the input string.

Input Size (n)	Approx. Operations
10	About 10 checks
100	About 100 checks
1000	About 1000 checks

Pattern observation: As the string gets longer, the work grows roughly in a straight line with the input size.

Final Time Complexity

Time Complexity: O(n)

This means the time to find a match grows linearly with the length of the input string.

Common Mistake

[X] Wrong: "preg_match always runs instantly no matter the input size."

[OK] Correct: The function must check characters one by one, so longer strings take more time.

Interview Connect

Understanding how pattern matching scales helps you write efficient code and explain your choices clearly in interviews.

Self-Check

"What if the pattern uses complex wildcards or backreferences? How would the time complexity change?"