Time Complexity: String replacement (${var/old/new})
O(n)
0
0
String replacement (${var/old/new}) in Bash Scripting - Time & Space Complexity
Understanding Time Complexity
We want to understand how the time it takes to replace text inside a string grows as the string gets longer.
How does the replacement operation scale when the input string size changes?
Scenario Under Consideration
Analyze the time complexity of the following code snippet.
text="hello world hello"
new_text=${text/hello/hi}
echo "$new_text"
This code replaces the first occurrence of "hello" with "hi" in the string stored in text.
Identify Repeating Operations
Identify the loops, recursion, array traversals that repeat.
- Primary operation: Scanning the string to find the first match of the pattern.
- How many times: The string is checked character by character until the first match is found or the string ends.
How Execution Grows With Input
The time to find the pattern grows roughly with the length of the string because it may need to check each character once.
| Input Size (n) | Approx. Operations |
|---|---|
| 10 | About 10 character checks |
| 100 | About 100 character checks |
| 1000 | About 1000 character checks |
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 grows directly with the length of the string.
Common Mistake
[X] Wrong: "String replacement happens instantly no matter how long the string is."
[OK] Correct: The command must scan the string to find the pattern, so longer strings take more time.
Interview Connect
Knowing how string operations scale helps you write scripts that stay fast even with big inputs.
Self-Check
"What if we replaced all occurrences instead of just the first? How would the time complexity change?"