Quantifiers (*, +, ?) in Bash Scripting - Time & Space Complexity

Time Complexity: Quantifiers (*, +, ?)

O(n)

Understanding Time Complexity

When using quantifiers like *, +, and ? in bash scripting, it's important to understand how they affect the number of operations performed.

We want to see how the script's work grows as input size changes when these quantifiers are used.

Scenario Under Consideration

Analyze the time complexity of the following bash script using quantifiers.

#!/bin/bash
input="$1"

if [[ $input =~ ^[a-z]*$ ]]; then
  echo "Only lowercase letters or empty"
fi

if [[ $input =~ ^[a-z]+$ ]]; then
  echo "At least one lowercase letter"
fi

if [[ $input =~ ^[a-z]?$ ]]; then
  echo "Zero or one lowercase letter"
fi

This script checks if the input matches patterns with *, +, and ? quantifiers.

Identify Repeating Operations

Look at what repeats when the script runs.

• Primary operation: The regex engine checks each character in the input string against the pattern.
• How many times: It processes each character once to match the pattern.

How Execution Grows With Input

The time to check the input grows as the input gets longer because each character is checked.

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

Pattern observation: The work grows linearly with input size.

Final Time Complexity

Time Complexity: O(n)

This means the time to run the regex grows directly with the length of the input string.

Common Mistake

[X] Wrong: "Quantifiers like * or + make the script run instantly no matter the input size."

[OK] Correct: Even with quantifiers, the regex engine must check each character, so longer inputs take more time.

Interview Connect

Understanding how quantifiers affect performance helps you write efficient scripts and explain your reasoning clearly in interviews.

Self-Check

"What if the regex pattern used nested quantifiers or backreferences? How would that affect time complexity?"