sed substitution in Linux CLI - Time & Space Complexity

Time Complexity: sed substitution

O(n)

Understanding Time Complexity

We want to understand how the time taken by a sed substitution command changes as the input size grows.

Specifically, how does sed handle replacing text in larger files?

Scenario Under Consideration

Analyze the time complexity of the following sed command.

sed 's/apple/orange/g' input.txt > output.txt

This command replaces every occurrence of "apple" with "orange" in the file input.txt and writes the result to output.txt.

Identify Repeating Operations

Look for repeated actions inside the command.

• Primary operation: sed reads each line of the file and scans for the pattern "apple" to replace.
• How many times: It processes every line once, and within each line, it checks every character to find matches.

How Execution Grows With Input

As the file gets bigger, sed must read more lines and check more 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 file size.

Final Time Complexity

Time Complexity: O(n)

This means the time sed takes grows linearly with the size of the input file.

Common Mistake

[X] Wrong: "sed substitution runs instantly no matter the file size because it's just a simple replace."

[OK] Correct: sed must read and check every part of the file, so bigger files take more time.

Interview Connect

Understanding how tools like sed scale with input size helps you write efficient scripts and shows you think about performance in real tasks.

Self-Check

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