Character classes ([a-z], [0-9]) in Bash Scripting - Time & Space Complexity

Time Complexity: Character classes ([a-z], [0-9])

O(n)

Understanding Time Complexity

We want to see how the time to run a bash script changes when it uses character classes like [a-z] or [0-9].

How does the script's work grow as the input size grows?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

#!/bin/bash
input="$1"
count=0
for (( i=0; i<${#input}; i++ )); do
  char=${input:i:1}
  if [[ $char =~ [a-z] ]]; then
    ((count++))
  fi
done

echo "Lowercase letters count: $count"
    

This script counts how many lowercase letters are in the input string using the [a-z] character class.

Identify Repeating Operations

• Primary operation: Looping through each character of the input string.
• How many times: Once for every character in the input (length n).

How Execution Grows With Input

Each character is checked once to see if it matches the [a-z] pattern.

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 directly with the input size. Double the input, double the checks.

Final Time Complexity

Time Complexity: O(n)

This means the script takes time proportional to the length of the input string.

Common Mistake

[X] Wrong: "Using character classes like [a-z] makes the script slower in a way that depends on the number of matches."

[OK] Correct: The script checks each character once regardless of matches, so time depends only on input length, not how many characters match.

Interview Connect

Understanding how pattern matching scales helps you write efficient scripts and explain your reasoning clearly in interviews.

Self-Check

"What if we changed the script to check for multiple character classes inside the loop? How would the time complexity change?"