Capturing groups and backreferences in PHP - Time & Space Complexity

Time Complexity: Capturing groups and backreferences

O(n)

Understanding Time Complexity

When using capturing groups and backreferences in PHP regular expressions, it's important to understand how the matching process grows as the input gets bigger.

We want to know how the time to find matches changes when the input string or pattern size increases.

Scenario Under Consideration

Analyze the time complexity of the following PHP code using capturing groups and backreferences.

$pattern = '/(\w+)\s\1/';
$input = 'word word word word word word word word word word';
if (preg_match($pattern, $input, $matches)) {
    echo "Match found: " . $matches[0];
} else {
    echo "No match found.";
}
    

This code looks for two identical words next to each other using a capturing group and a backreference.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The regex engine tries to match the pattern at each position in the input string.
• How many times: It attempts matching starting from each character in the input until a match is found or input ends.

How Execution Grows With Input

As the input string gets longer, the regex engine tries more starting points to find the pattern.

Input Size (n)	Approx. Operations
10	About 10 attempts to match
100	About 100 attempts to match
1000	About 1000 attempts to match

Pattern observation: The number of attempts grows roughly in direct proportion to 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: "Backreferences always make regex run in constant time."

[OK] Correct: Backreferences can cause the regex engine to try many positions, so time usually grows with input size, not stay fixed.

Interview Connect

Understanding how capturing groups and backreferences affect performance helps you write efficient patterns and explain your code clearly in interviews.

Self-Check

"What if we changed the pattern to use nested capturing groups with backreferences? How would the time complexity change?"