Time Complexity: Gsub with regex
O(n)
0
0
Gsub with regex in Ruby - Time & Space Complexity
Understanding Time Complexity
When using gsub with a regular expression in Ruby, it's important to understand how the time taken grows as the input string gets longer.
We want to know how the number of operations changes when the string size increases.
Scenario Under Consideration
Analyze the time complexity of the following code snippet.
text = "hello world hello"
pattern = /hello/
result = text.gsub(pattern, "hi")
puts result
This code replaces all occurrences of "hello" with "hi" in the given text string.
Identify Repeating Operations
Identify the loops, recursion, array traversals that repeat.
- Primary operation: Scanning the entire string to find matches for the regex pattern.
- How many times: Each character in the string is checked once or a few times depending on the regex engine.
How Execution Grows With Input
As the input string gets longer, the time to scan and replace grows roughly in direct proportion to the string length.
| Input Size (n) | Approx. Operations |
|---|---|
| 10 | About 10 checks |
| 100 | About 100 checks |
| 1000 | About 1000 checks |
Pattern observation: The work grows steadily as the string gets longer, roughly one check per character.
Final Time Complexity
Time Complexity: O(n)
This means the time to complete the replacement grows in a straight line with the length of the input string.
Common Mistake
[X] Wrong: "Using regex with gsub always takes the same time no matter how long the string is."
[OK] Correct: The regex engine must check each part of the string to find matches, so longer strings take more time.
Interview Connect
Understanding how string operations like gsub scale helps you write efficient code and explain your choices clearly in interviews.
Self-Check
"What if the regex pattern was more complex, like including wildcards or repetitions? How would that affect the time complexity?"