sed for substitution in scripts in Bash Scripting - Time & Space Complexity

Time Complexity: sed for substitution in scripts

O(n)

Understanding Time Complexity

When using sed for substitution in scripts, it is important to understand how the time it takes grows as the input size increases.

We want to know how the execution time changes when the input file or text gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following sed substitution command in a script.

sed 's/old/new/g' input.txt > output.txt
    

This command replaces all occurrences of the word "old" with "new" in the file input.txt and writes the result to output.txt.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: sed reads each line of the input file one by one.
• How many times: It processes every line and checks each character for matches to replace.

How Execution Grows With Input

As the input file grows, sed must check more lines and characters.

Input Size (n lines)	Approx. Operations
10	Checks all characters in 10 lines
100	Checks all characters in 100 lines
1000	Checks all characters in 1000 lines

Pattern observation: The work grows roughly in direct proportion to the number of lines and characters in the input.

Final Time Complexity

Time Complexity: O(n)

This means the time to complete the substitution grows linearly with the size of the input file.

Common Mistake

[X] Wrong: "The substitution runs instantly no matter the file size."

[OK] Correct: The command must read and check every character, so bigger files take more time.

Interview Connect

Understanding how tools like sed scale with input size helps you write efficient scripts and explain your choices clearly in interviews.

Self-Check

What if we used sed to substitute only the first occurrence per line instead of all occurrences? How would the time complexity change?