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?"

Practice

1. What does the sed command sed 's/cat/dog/' file.txt do?

easy

A. Deletes all lines containing 'cat' in file.txt

B. Replaces the first occurrence of 'cat' with 'dog' on each line of file.txt

C. Prints only lines containing 'dog' from file.txt

D. Appends 'dog' at the end of each line containing 'cat' in file.txt

Solution

1. Step 1: Understand the substitution command

   The s/pattern/replacement/ syntax in sed replaces the first match of 'pattern' with 'replacement' on each line.

2. Step 2: Apply to the given command

   The command replaces the first occurrence of 'cat' with 'dog' on every line of file.txt.

3. Final Answer:

   Replaces the first occurrence of 'cat' with 'dog' on each line of file.txt -> Option B

4. Quick Check:

   sed substitution = replace first match [OK]

Hint: Remember: s/pattern/replacement/ changes first match per line [OK]

Common Mistakes:

• Thinking it deletes lines instead of substituting
• Assuming it replaces all occurrences without 'g' flag
• Confusing printing lines with substitution

2. Which of the following is the correct syntax to delete all lines containing the word 'error' using sed?

easy

A. sed '/error/d' filename

B. sed 'd/error/' filename

C. sed 's/error/d/' filename

D. sed 'delete /error/' filename

Solution

1. Step 1: Identify the delete command syntax in sed

   To delete lines matching a pattern, the syntax is sed '/pattern/d'.

2. Step 2: Match the correct option

   sed '/error/d' filename uses sed '/error/d', which deletes lines containing 'error'. Other options have incorrect syntax.

3. Final Answer:

   sed '/error/d' filename -> Option A

4. Quick Check:

   Delete lines with pattern = /pattern/d [OK]

Hint: Use '/pattern/d' to delete matching lines in sed [OK]

Common Mistakes:

• Placing 'd' before the pattern
• Using substitution syntax instead of delete
• Writing 'delete' instead of 'd'

3. What is the output of the command echo 'apple banana apple' | sed 's/apple/orange/g'?

medium

A. orange banana orange

B. orange banana apple

C. apple banana apple

D. apple banana orange

Solution

1. Step 1: Understand the 'g' flag in substitution

   The 'g' flag means replace all occurrences of the pattern on each line, not just the first.

2. Step 2: Apply substitution to the input string

   All 'apple' words are replaced by 'orange', so 'apple banana apple' becomes 'orange banana orange'.

3. Final Answer:

   orange banana orange -> Option A

4. Quick Check:

   Substitute all matches with 'g' flag = replaced all [OK]

Hint: Add 'g' to replace all matches, not just first [OK]

Common Mistakes:

• Forgetting the 'g' flag replaces only first occurrence
• Confusing output with original input
• Misreading the pipe input

4. Identify the error in this sed command: sed 's/hello/goodbye' file.txt

medium

A. No error; command is correct

B. Incorrect command; 's' cannot be used with text files

C. The pattern 'hello' is invalid

D. Missing delimiter after replacement text

Solution

1. Step 1: Check the substitution syntax

   The substitution command requires delimiters: s/pattern/replacement/. The final '/' is missing here.

2. Step 2: Identify the missing delimiter

   The command ends with 's/hello/goodbye' missing the closing '/' delimiter after 'goodbye'.

3. Final Answer:

   Missing delimiter after replacement text -> Option D

4. Quick Check:

   Substitution needs closing '/' delimiter [OK]

Hint: Check that substitution ends with '/' delimiter [OK]

Common Mistakes:

• Omitting the last '/' in substitution
• Assuming 's' can't be used on files
• Thinking pattern must be a regex error

5. You want to replace the word 'cat' with 'dog' only on lines 2 to 4 in a file named pets.txt. Which sed command achieves this?

hard

A. sed 's/cat/dog/ 2,4' pets.txt

B. sed '/2,4 s/cat/dog/' pets.txt

C. sed '2,4s/cat/dog/' pets.txt

D. sed 's/cat/dog/ 2-4' pets.txt

Solution

1. Step 1: Understand address range in sed

   To apply a command only on specific lines, use start,endcommand syntax, e.g., 2,4s/pattern/replacement/.

2. Step 2: Match the correct syntax

   sed '2,4s/cat/dog/' pets.txt correctly uses 2,4s/cat/dog/ to replace 'cat' with 'dog' on lines 2 to 4.

3. Final Answer:

   sed '2,4s/cat/dog/' pets.txt -> Option C

4. Quick Check:

   Use line range before command to limit sed action [OK]

Hint: Use 'start,end' before 's' to limit substitution lines [OK]

Common Mistakes:

• Placing line numbers after substitution command
• Using incorrect range syntax like '2-4'
• Adding slashes around line numbers