Time Complexity: Preg_replace for substitution
O(n)
0
0
Preg_replace for substitution in PHP - Time & Space Complexity
Understanding Time Complexity
When using preg_replace in PHP, it's important to know how the time it takes grows as the input gets bigger.
We want to understand how the number of replacements affects the work done.
Scenario Under Consideration
Analyze the time complexity of the following code snippet.
$string = "apple banana apple grape apple";
$pattern = '/apple/';
$replacement = 'orange';
$result = preg_replace($pattern, $replacement, $string);
This code replaces every occurrence of "apple" with "orange" in the given string.
Identify Repeating Operations
Identify the loops, recursion, array traversals that repeat.
- Primary operation: The function scans the entire string to find matches for the pattern.
- How many times: It checks each character in the string, and for each match, it performs a replacement.
How Execution Grows With Input
The time taken grows roughly in proportion to the length of the string because every character is checked.
| Input Size (n) | Approx. Operations |
|---|---|
| 10 | About 10 checks |
| 100 | About 100 checks |
| 1000 | About 1000 checks |
Pattern observation: Doubling the string length roughly doubles the work done.
Final Time Complexity
Time Complexity: O(n)
This means the time to complete grows linearly with the size of the input string.
Common Mistake
[X] Wrong: "preg_replace runs in constant time no matter the string size."
[OK] Correct: The function must check each character to find matches, so bigger strings take more time.
Interview Connect
Understanding how pattern matching scales helps you explain performance when working with text processing in real projects.
Self-Check
"What if the pattern was more complex and used backreferences? How would that affect the time complexity?"