Character classes and quantifiers in PHP - Time & Space Complexity

Time Complexity: Character classes and quantifiers

O(n)

Understanding Time Complexity

When using character classes and quantifiers in PHP regular expressions, it's important to understand how the matching process scales as the input grows.

We want to know how the time to find matches changes when the input string gets longer.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

$pattern = '/[a-z]{3,5}/';
$input = str_repeat('abc', 1000);
if (preg_match_all($pattern, $input, $matches)) {
    // matches found
}
    

This code searches for sequences of 3 to 5 lowercase letters in a long repeated string.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The regex engine checks each position in the input string to see if the pattern matches.
• How many times: It tries to match starting at almost every character, so roughly once per character in the input.

How Execution Grows With Input

As the input string gets longer, the regex engine does more checks, roughly one per character.

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

Pattern observation: The work grows roughly in direct proportion to the input size.

Final Time Complexity

Time Complexity: O(n)

This means the time to find matches grows linearly as the input string gets longer.

Common Mistake

[X] Wrong: "Using quantifiers always makes regex slow and exponential."

[OK] Correct: Simple quantifiers like {3,5} on character classes usually cause only linear checks, not exponential backtracking.

Interview Connect

Understanding how regex matching time grows helps you write efficient patterns and explain your code clearly in interviews.

Self-Check

"What if we changed the quantifier from {3,5} to .*? How would the time complexity change?"