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

Practice

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

easy

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

B. Replaces all occurrences of 'cat' with 'dog' in the entire file.txt

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

D. Prints lines containing 'dog' from file.txt

Solution

1. Step 1: Understand the sed substitution syntax

   The command sed 's/cat/dog/' file.txt uses s/pattern/replacement/ which replaces the first match per line.

2. Step 2: Apply the command to the file

   It replaces only the first 'cat' found on each line with 'dog', not all occurrences or lines.

3. Final Answer:

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

4. Quick Check:

   sed s/pattern/replacement/ replaces first match per line [OK]

Hint: No 'g' flag means only first match per line replaced [OK]

Common Mistakes:

• Thinking all matches are replaced without 'g'
• Confusing substitution with deletion
• Assuming it prints only matching lines

2. Which of the following is the correct syntax to replace all occurrences of 'apple' with 'orange' using sed?

easy

A. sed 's/apple/orange/' file.txt

B. sed 's/apple/orange/g' file.txt

C. sed 's/apple/orange/g;' file.txt

D. sed 's/apple/orange/gp' file.txt

Solution

1. Step 1: Identify the flag for global replacement

   The 'g' flag after the substitution pattern tells sed to replace all occurrences on each line.

2. Step 2: Check syntax correctness

   sed 's/apple/orange/g' file.txt uses sed 's/apple/orange/g' which is the correct syntax without extra characters.

3. Final Answer:

   sed 's/apple/orange/g' file.txt -> Option B

4. Quick Check:

   'g' flag means replace all matches per line [OK]

Hint: Add 'g' after last slash to replace all matches [OK]

Common Mistakes:

• Omitting the 'g' flag for all replacements
• Adding extra semicolons inside quotes
• Using 'gp' which is invalid here

3. What is the output of this command if input.txt contains:

apple apple banana
banana apple apple

sed 's/apple/orange/' input.txt?

medium

A. orange orange banana
banana orange orange

B. orange apple banana
banana apple apple

C. orange apple banana
banana orange apple

D. apple apple banana
banana apple apple

Solution

1. Step 1: Understand sed substitution without 'g'

   Without 'g', only the first 'apple' on each line is replaced by 'orange'.

2. Step 2: Apply substitution line by line

   Line 1: 'apple apple banana' becomes 'orange apple banana'. Line 2: 'banana apple apple' becomes 'banana orange apple'.

3. Final Answer:

   orange apple banana banana orange apple -> Option C

4. Quick Check:

   First match per line replaced only [OK]

Hint: No 'g' means only first match per line changes [OK]

Common Mistakes:

• Replacing all 'apple' without 'g'
• Replacing none due to misunderstanding
• Confusing line order or content

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

medium

A. File name should come before the command

B. Incorrect delimiter used

C. Missing 'g' flag for global replacement

D. Missing closing quote after 'g'

Solution

1. Step 1: Check the quotes in the command

   The command has an opening single quote before s/hello/world/g but no closing quote after 'g'.

2. Step 2: Confirm correct placement of quotes and arguments

   The file name should be outside the quotes. The missing closing quote causes syntax error.

3. Final Answer:

   Missing closing quote after 'g' -> Option D

4. Quick Check:

   Quotes must enclose entire sed expression [OK]

Hint: Always close quotes around sed expression [OK]

Common Mistakes:

• Placing file name inside quotes
• Forgetting closing quote
• Confusing delimiter with quotes

5. You want to replace all occurrences of 'foo' with 'bar' only on lines containing 'baz' in data.txt. Which command achieves this?

hard

A. sed '/baz/ s/foo/bar/g' data.txt

B. sed 's/foo/bar/g /baz/' data.txt

C. sed 's/foo/bar/g' data.txt | grep baz

D. sed '/foo/ s/baz/bar/g' data.txt

Solution

1. Step 1: Understand address restriction in sed

   Using /baz/ s/foo/bar/g applies substitution only on lines matching 'baz'.

2. Step 2: Verify command correctness

   sed '/baz/ s/foo/bar/g' data.txt correctly restricts substitution to lines with 'baz' and replaces all 'foo' with 'bar'.

3. Final Answer:

   sed '/baz/ s/foo/bar/g' data.txt -> Option A

4. Quick Check:

   Address before command limits lines affected [OK]

Hint: Use /pattern/ before s/// to limit lines [OK]

Common Mistakes:

• Placing substitution after file name
• Using grep after sed instead of address
• Mixing patterns in wrong order