sed (stream editor) basics in Linux CLI - Time & Space Complexity

Time Complexity: sed (stream editor) basics

O(n)

Understanding Time Complexity

When using sed, it processes text line by line. Understanding how its work grows with input size helps us predict how long it will take on bigger files.

We want to know: how does the time to run sed change as the number of lines grows?

Scenario Under Consideration

Analyze the time complexity of the following sed command.

sed 's/foo/bar/g' input.txt > output.txt

This command replaces every occurrence of "foo" with "bar" in each line of the file.

Identify Repeating Operations

Look at what repeats as the command runs:

• Primary operation: Reading and processing each line one by one.
• How many times: Once for every line in the input file.

How Execution Grows With Input

As the file gets bigger, sed works through more lines, doing the same replace on each.

Input Size (n)	Approx. Operations
10 lines	10 replace checks
100 lines	100 replace checks
1000 lines	1000 replace checks

Pattern observation: The work grows directly with the number of lines. Double the lines, double the work.

Final Time Complexity

Time Complexity: O(n)

This means the time sed takes grows in a straight line with the number of lines it processes.

Common Mistake

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

[OK] Correct: Even simple commands must read and check every line. More lines mean more work and more time.

Interview Connect

Knowing how sed scales helps you write scripts that handle big files efficiently. It shows you understand how tools behave with growing data, a key skill in scripting.

Self-Check

"What if we changed the command to only replace on lines matching a pattern? How would the time complexity change?"