String replacement in MATLAB - Time & Space Complexity

Time Complexity: String replacement

O(n*m)

Understanding Time Complexity

We want to understand how the time it takes to replace parts of a string changes as the string gets longer.

How does the work grow when we replace text inside a bigger string?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

originalStr = "hello world hello";
searchStr = "hello";
replaceStr = "hi";
newStr = strrep(originalStr, searchStr, replaceStr);

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 original string to find all matches of the search string.
• How many times: The scan goes through the entire string once, checking each position for a match.

How Execution Grows With Input

As the string gets longer, the function checks more positions 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*m)

This means the time to replace text grows linearly with the product of the string length and the search string length.

Common Mistake

[X] Wrong: "Replacing text takes the same time no matter how long the string is."

[OK] Correct: The function must check each part of the string, so longer strings take more time.

Interview Connect

Understanding how string operations grow with input size helps you explain your code choices clearly and confidently.

Self-Check

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