Regex in [[ ]] with =~ in Bash Scripting - Time & Space Complexity

Time Complexity: Regex in [[ ]] with =~

O(n)

Understanding Time Complexity

When using regex inside [[ ]] with =~ in bash, it is important to understand how the time to check a match grows as the input changes.

We want to know how the script's running time changes when the input string gets longer.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

input="$1"
pattern='^[a-z]+$'

if [[ $input =~ $pattern ]]; then
  echo "Match found"
else
  echo "No match"
fi
    

This code checks if the input string contains only lowercase letters using a regex match inside [[ ]] with =~.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The regex engine scans each character of the input string to check if it matches the pattern.
• How many times: It processes each character once, moving through the string from start to end.

How Execution Grows With Input

As the input string gets longer, the regex engine checks more characters one by one.

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

Pattern observation: The time to check grows roughly in a straight line with the input length.

Final Time Complexity

Time Complexity: O(n)

This means the time to check the regex match grows linearly with the length of the input string.

Common Mistake

[X] Wrong: "Regex matching inside [[ ]] with =~ is instant no matter how long the input is."

[OK] Correct: The regex engine must look at each character to confirm a match, so longer inputs take more time.

Interview Connect

Understanding how regex matching time grows helps you write efficient scripts and explain your code clearly in interviews.

Self-Check

"What if the regex pattern included nested quantifiers or backreferences? How would the time complexity change?"