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