Gsub and sub for replacement in Ruby - Time & Space Complexity

Time Complexity: Gsub and sub for replacement

O(n)

Understanding Time Complexity

When we use sub or gsub in Ruby, we want to know how the time to replace text grows as the text gets longer.

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

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

text = "hello hello hello"
result_sub = text.sub("hello", "hi")
result_gsub = text.gsub("hello", "hi")
    

This code replaces the first occurrence of "hello" with "hi" using sub, and all occurrences using gsub.

Identify Repeating Operations

Look at what repeats when replacing text:

• Primary operation: Scanning the string to find matches of the target text.
• How many times: For sub, it stops after the first match; for gsub, it continues scanning the whole string to replace all matches.

How Execution Grows With Input

As the string gets longer, the time to scan grows roughly with the string length.

Input Size (n)	Approx. Operations
10	About 10 checks for matches
100	About 100 checks for matches
1000	About 1000 checks for matches

Pattern observation: The work grows in a straight line as the string gets longer.

Final Time Complexity

Time Complexity: O(n)

This means the time to replace text grows directly with the length of the string.

Common Mistake

[X] Wrong: "gsub is always much slower than sub because it replaces all matches."

[OK] Correct: Both scan the string, but gsub continues scanning after the first match, so the difference depends on how many matches there are, not just the method itself.

Interview Connect

Understanding how string replacement scales helps you write efficient code and explain your choices clearly in real projects or interviews.

Self-Check

What if we used a regular expression with gsub instead of a simple string? How would the time complexity change?