Preg_match_all for global matching in PHP - Time & Space Complexity

Time Complexity: Preg_match_all for global matching

O(n)

Understanding Time Complexity

We want to understand how the time it takes to find all matches in a string grows as the string gets longer.

How does the number of matches and string length affect the work done?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

$pattern = '/\d+/';
$text = 'There are 123 apples and 4567 oranges.';
preg_match_all($pattern, $text, $matches);
// $matches will hold all groups of digits found in $text
    

This code finds all groups of digits in a text string and stores them.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Scanning each character in the input string to find matches.
• How many times: Once for each character in the string, plus extra work for each match found.

How Execution Grows With Input

As the string gets longer, the function checks more characters to find matches.

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 string length.

Final Time Complexity

Time Complexity: O(n)

This means the time to find all matches grows linearly with the length of the input string.

Common Mistake

[X] Wrong: "preg_match_all runs in constant time no matter the string size."

[OK] Correct: The function must check each character to find matches, so longer strings take more time.

Interview Connect

Understanding how pattern matching scales helps you write efficient code when working with text data.

Self-Check

"What if the pattern was more complex, like including optional parts or repetitions? How would the time complexity change?"