Time Complexity: String suffix removal (${var%pattern})
O(n)
0
0
String suffix removal (${var%pattern}) in Bash Scripting - Time & Space Complexity
Understanding Time Complexity
We want to understand how long it takes to remove a suffix from a string using bash's ${var%pattern} syntax.
Specifically, how does the time needed change as the string or pattern size grows?
Scenario Under Consideration
Analyze the time complexity of the following code snippet.
string="filename_backup_2024.txt"
pattern="*.txt"
result=${string%$pattern}
echo "$result"
This code removes the shortest suffix matching the pattern from the string.
Identify Repeating Operations
Identify the loops, recursion, array traversals that repeat.
- Primary operation: Matching the pattern against the string suffix.
- How many times: The shell checks suffixes from the end of the string, moving backward until a match is found.
How Execution Grows With Input
As the string length grows, the shell tries more suffixes to find a match.
| Input Size (n) | Approx. Operations |
|---|---|
| 10 | Up to 10 suffix checks |
| 100 | Up to 100 suffix checks |
| 1000 | Up to 1000 suffix checks |
Pattern observation: The number of checks grows roughly in direct proportion to the string length.
Final Time Complexity
Time Complexity: O(n)
This means the time to remove the suffix grows linearly with the string length.
Common Mistake
[X] Wrong: "The suffix removal happens instantly no matter how long the string is."
[OK] Correct: The shell must check suffixes step by step, so longer strings take more time.
Interview Connect
Understanding how string operations scale helps you write efficient scripts and explain your reasoning clearly in interviews.
Self-Check
"What if we used the longest suffix removal syntax ${var%%pattern} instead? How would the time complexity change?"