Anchors (^, $) in Bash Scripting - Time & Space Complexity

Time Complexity: Anchors (^, $)

O(n)

Understanding Time Complexity

When using anchors like ^ and $ in bash scripting, we want to know how the script's speed changes as input grows.

We ask: How does matching lines with anchors affect the time it takes?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

#!/bin/bash

pattern='^hello$'

while IFS= read -r line; do
  if [[ $line =~ $pattern ]]; then
    echo "Match: $line"
  fi
done < input.txt

This script reads each line from a file and checks if it exactly matches the word "hello" using anchors.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Reading each line and testing it against the anchored pattern.
• How many times: Once for every line in the input file.

How Execution Grows With Input

Each new line adds one more pattern check, so the work grows steadily with the number of lines.

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

Pattern observation: The time grows directly with the number of lines; double the lines, double the checks.

Final Time Complexity

Time Complexity: O(n)

This means the script takes longer in a straight line as the input file gets bigger.

Common Mistake

[X] Wrong: "Anchors make the script run faster because they limit matches."

[OK] Correct: Anchors only change what matches, not how many lines are checked. The script still tests every line.

Interview Connect

Understanding how pattern matching scales helps you write scripts that stay fast even with big files. This skill shows you can think about efficiency clearly.

Self-Check

"What if we changed the pattern to match anywhere in the line without anchors? How would the time complexity change?"

Practice

1. What does the anchor ^ represent in a bash regular expression?

easy

A. It matches the end of a line.

B. It matches any digit.

C. It matches any whitespace character.

D. It matches the start of a line.

Solution

1. Step 1: Understand the role of anchors in regex

   Anchors are special characters that match positions in text, not actual characters.

2. Step 2: Identify the meaning of ^

   The ^ anchor matches the start of a line in bash regex.

3. Final Answer:

   It matches the start of a line. -> Option D

4. Quick Check:

   ^ means start of line [OK]

Hint: Remember ^ means start, $ means end of line [OK]

Common Mistakes:

• Confusing ^ with end of line anchor
• Thinking ^ matches a character instead of position
• Mixing ^ with other regex symbols like * or .

2. Which of the following grep commands correctly finds lines that end with the word done?

easy

A. grep 'done$' file.txt

B. grep '^done' file.txt

C. grep 'done^' file.txt

D. grep '^done$' file.txt

Solution

1. Step 1: Understand the meaning of $ anchor

   The $ anchor matches the end of a line in regex.

2. Step 2: Match lines ending with 'done'

   Using done$ matches lines where 'done' is at the end.

3. Final Answer:

   grep 'done$' file.txt -> Option A

4. Quick Check:

   Use $ to match line end [OK]

Hint: Use $ after text to match line endings [OK]

Common Mistakes:

• Using ^ after text instead of $
• Using ^done to match line end
• Confusing ^ and $ anchors

3. What will be the output of this command if file.txt contains the lines:

apple
banana
apple pie
pineapple
apple

grep '^apple$' file.txt

medium

A. apple
apple pie
apple

B. apple pie
pineapple

C. apple
apple

D. banana

Solution

1. Step 1: Understand the regex ^apple$

   This matches lines that start and end exactly with 'apple' and nothing else.

2. Step 2: Check each line in file.txt

   Lines 'apple' and 'apple' match exactly. 'apple pie' and 'pineapple' do not match because of extra text.

3. Final Answer:

   apple apple -> Option C

4. Quick Check:

   ^ and $ match exact whole line [OK]

Hint: Use ^ and $ together to match whole exact lines [OK]

Common Mistakes:

• Assuming partial matches with anchors
• Ignoring that $ matches end of line
• Confusing lines with extra words as matches

4. You wrote this command to find lines starting with 'Error' in a log file:
grep 'Error^' logfile.txt
But it returns no results. What is the problem?

medium

A. The file does not contain 'Error'.

B. The anchor ^ should be at the start, not after 'Error'.

C. grep does not support anchors like ^.

D. The command needs double quotes instead of single quotes.

Solution

1. Step 1: Analyze the position of the anchor ^

   The ^ anchor must be at the start of the pattern to match line start.

2. Step 2: Correct the pattern placement

   Use ^Error to match lines starting with 'Error'. Placing ^ after 'Error' is invalid.

3. Final Answer:

   The anchor ^ should be at the start, not after 'Error'. -> Option B

4. Quick Check:

   ^ must be at pattern start [OK]

Hint: Place ^ only at pattern start to match line start [OK]

Common Mistakes:

• Putting ^ after text instead of before
• Assuming grep ignores anchors
• Using wrong quotes causing shell issues

5. You want to extract lines from data.txt that start with a digit and end with a period. Which grep pattern correctly uses anchors to do this?

hard

A. grep '^[0-9].*\.$' data.txt

B. grep '^[0-9].*$' data.txt

C. grep '^\d.*\.$' data.txt

D. grep '^[0-9].*.$' data.txt

Solution

1. Step 1: Match line start with a digit

   The pattern ^[0-9] matches lines starting with any digit.

2. Step 2: Match line end with a literal period

   Use \.$ to match a literal '.' at the end. The dot must be escaped to avoid matching any character.

3. Step 3: Combine pattern correctly

   ^[0-9].*\.$ matches lines starting with digit, any characters, ending with a period.

4. Final Answer:

   grep '^[0-9].*\.$' data.txt -> Option A

5. Quick Check:

   ^ start, $ end, escape . for literal dot [OK]

Hint: Escape dot to match literal period at line end [OK]

Common Mistakes:

• Not escaping dot, matching any char instead of period
• Using \d which grep may not support by default
• Missing $ anchor at line end