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?

Practice

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

easy

A. Prints lines containing 'cat' from file.txt

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

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

D. Deletes all lines containing 'cat' from file.txt

Solution

1. Step 1: Understand the sed substitution syntax

   The command sed 's/cat/dog/' file.txt uses s/old/new/ which replaces only the first match per line.

2. Step 2: Apply to the file content

   Each line in file.txt will have its first 'cat' replaced by 'dog', other occurrences remain unchanged.

3. Final Answer:

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

4. Quick Check:

   sed s/old/new/ replaces first match per line [OK]

Hint: Remember: no 'g' means only first match replaced per line [OK]

Common Mistakes:

• Thinking it replaces all matches 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' in a file using sed?

easy

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

B. sed 'replace apple with orange' file.txt

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

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

Solution

1. Step 1: Identify the global flag usage

   To replace all occurrences on each line, the 'g' flag is needed after the substitution pattern.

2. Step 2: Check each option

   sed 's/apple/orange/g' file.txt uses s/apple/orange/g which correctly replaces all 'apple' with 'orange'. sed 's/apple/orange/' file.txt replaces only first occurrence. sed 'replace apple with orange' file.txt is invalid syntax. sed 's/apple/orange//g' file.txt has extra slashes causing syntax error.

3. Final Answer:

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

4. Quick Check:

   Use 'g' flag for all matches [OK]

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

Common Mistakes:

• Omitting the 'g' flag to replace all matches
• Adding extra slashes causing syntax errors
• Using incorrect command words like 'replace'

3. What will be the output of the following command if the input file contains the line apple apple apple?

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

medium

A. orange orange orange

B. orange apple apple

C. apple orange apple

D. apple apple orange

Solution

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

   Without the 'g' flag, sed replaces only the first occurrence of 'apple' per line.

2. Step 2: Apply substitution to the input line

   The first 'apple' becomes 'orange', the rest remain unchanged, resulting in 'orange apple apple'.

3. Final Answer:

   orange apple apple -> Option B

4. Quick Check:

   First match replaced only without 'g' [OK]

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

Common Mistakes:

• Assuming all occurrences change without 'g'
• Confusing order of words after substitution
• Thinking sed changes input file by default

4. You wrote this sed command to replace 'foo' with 'bar' globally: sed 's/foo/bar/' file.txt. But only the first 'foo' per line is replaced. What is the fix?

medium

A. Add the 'g' flag: sed 's/foo/bar/g' file.txt

B. Use double quotes instead of single quotes

C. Add a space after 'bar/'

D. Use sed -i option to edit in place

Solution

1. Step 1: Identify missing global flag

   The command lacks the 'g' flag, so only first occurrence per line is replaced.

2. Step 2: Add the 'g' flag to fix

   Adding 'g' after the substitution pattern makes sed replace all occurrences per line.

3. Final Answer:

   Add the 'g' flag: sed 's/foo/bar/g' file.txt -> Option A

4. Quick Check:

   Global flag 'g' replaces all matches [OK]

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

Common Mistakes:

• Thinking quotes affect substitution behavior
• Adding spaces inside substitution pattern
• Confusing in-place edit with substitution flags

5. You want to replace the word 'error' with 'warning' only on lines containing 'log' in a file. Which sed command achieves this?

hard

A. sed '/log/ s/error/warning/g' file.txt

B. sed 's/error/warning/g /log/' file.txt

C. sed 's/error/warning/g if /log/' file.txt

D. sed 's/error/warning/g' file.txt | grep log

Solution

1. Step 1: Understand conditional substitution in sed

   To apply substitution only on lines matching a pattern, use /pattern/ s/old/new/flags syntax.

2. Step 2: Analyze options

   sed '/log/ s/error/warning/g' file.txt correctly applies substitution only on lines containing 'log'. Options A and C have invalid syntax. sed 's/error/warning/g' file.txt | grep log replaces everywhere then filters lines, which does not limit substitution.

3. Final Answer:

   sed '/log/ s/error/warning/g' file.txt -> Option A

4. Quick Check:

   Use address before s/// to limit lines [OK]

Hint: Put pattern before s/// to restrict substitution lines [OK]

Common Mistakes:

• Placing substitution after pattern incorrectly
• Trying to use if statements inside sed
• Filtering lines after substitution instead of limiting it