String replace functions in PHP - Time & Space Complexity

Time Complexity: String replace functions

O(n)

Understanding Time Complexity

When we use string replace functions, we want to know how the time it takes changes as the string gets longer.

We ask: How does the work grow when the input string grows?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

$string = "hello world hello";
$search = "hello";
$replace = "hi";

$result = str_replace($search, $replace, $string);
    

This code replaces all occurrences of "hello" with "hi" in the given string.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Scanning the entire string to find matches of the search word.
• How many times: The function checks each character in the string once or more to find all matches.

How Execution Grows With Input

As the string gets longer, the function needs to look at 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 replace grows linearly as the string gets longer.

Common Mistake

[X] Wrong: "Replacing a word in a string always takes the same time no matter how long the string is."

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

Interview Connect

Understanding how string operations scale helps you write efficient code and explain your choices clearly in interviews.

Self-Check

"What if we replaced multiple different words at once? How would the time complexity change?"