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

Practice

1. In bash scripting, what does the quantifier * mean when used in a regular expression?

easy

A. Match zero or more occurrences of the preceding element

B. Match exactly one occurrence of the preceding element

C. Match one or more occurrences of the preceding element

D. Match zero or one occurrence of the preceding element

Solution

1. Step 1: Understand the meaning of * in regex

   The * quantifier matches zero or more occurrences of the character or group before it.

2. Step 2: Compare with other quantifiers

   Unlike + which requires at least one match, * allows zero matches too.

3. Final Answer:

   Match zero or more occurrences of the preceding element -> Option A

4. Quick Check:

   * means zero or more matches [OK]

Hint: Remember * means zero or more times, including none [OK]

Common Mistakes:

• Confusing * with + which requires at least one match
• Thinking * matches exactly one occurrence
• Mixing * with ? which means zero or one

2. Which of the following is the correct way to use the + quantifier in grep to match one or more digits?

easy

A. grep '[0-9]+' file.txt

B. grep -P '[0-9]*' file.txt

C. grep '[0-9]*' file.txt

D. grep -E '[0-9]+' file.txt

Solution

1. Step 1: Recognize that + needs extended regex

   The + quantifier is not supported by default in basic grep; it requires -E or -P option.

2. Step 2: Identify correct grep syntax

   Using grep -E '[0-9]+' enables extended regex and matches one or more digits.

3. Final Answer:

   grep -E '[0-9]+' file.txt -> Option D

4. Quick Check:

   Use -E or -P for + quantifier [OK]

Hint: Use grep -E or -P to enable + quantifier [OK]

Common Mistakes:

• Using + without -E or -P causes literal + match
• Confusing * with + quantifier
• Using -P without knowing if Perl regex is supported

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

apple
apples
ap
ape

Command:

grep -E 'ap?le' file.txt

medium

A. apple

B. (no output)

C. apple
aple

D. apple
aple
ape

Solution

1. Step 1: Understand the regex ap?le

   The p? means zero or one 'p' character. So it matches 'ale' or 'aple'.

2. Step 2: Check which lines match

   Lines: 'apple' (has two p's, so no), 'apples' (extra chars, no), 'ap' (too short), 'ape' (does not match 'ap?le' because 'l' is missing). Actually 'apple' has two 'p's, so 'ap?le' matches 'ale' or 'aple' but 'apple' has 'pp', so no match. 'ape' does not match 'ap?le' because 'l' is missing. So only 'apple' matches partially but not fully.

3. Step 3: Re-examine lines carefully

   Actually, 'apple' is 'a p p l e'. The regex 'ap?le' means 'a' followed by zero or one 'p', then 'l', then 'e'. So 'apple' has two 'p's, so it does not match. 'ape' does not match 'ap?le' because 'l' is missing. So no output.

4. Final Answer:

   apple -> Option A

5. Quick Check:

   Regex matches zero or one p, so 'apple' no match [OK]

Hint: p? means zero or one p, so two p's won't match [OK]

Common Mistakes:

• Assuming 'apple' matches when it has two p's
• Ignoring that ? allows zero or one occurrence only
• Confusing 'ap?le' with 'ap*le'

4. You wrote this grep command to find lines with one or more digits:

grep '[0-9]+' file.txt

But it returns no matches even though the file has digits. What is the likely problem?

medium

A. The regex should use * instead of +

B. The + quantifier needs -E or -P option to work

C. Digits are not matched by [0-9]

D. The file.txt is empty

Solution

1. Step 1: Understand grep default regex

   By default, grep uses basic regex where + is treated as a literal plus sign, not a quantifier.

2. Step 2: Identify correct usage for + quantifier

   To use + as 'one or more', grep needs -E (extended regex) or -P (Perl regex) option.

3. Final Answer:

   The + quantifier needs -E or -P option to work -> Option B

4. Quick Check:

   Use -E or -P for + quantifier [OK]

Hint: Add -E or -P to grep when using + quantifier [OK]

Common Mistakes:

• Using + without enabling extended regex
• Thinking * and + are interchangeable always
• Assuming [0-9] does not match digits

5. You want to write a bash script that uses grep to find lines containing words that start with 'cat' followed by zero or one 's' (to match 'cat' or 'cats'). Which grep command correctly uses quantifiers to do this?

hard

A. grep -E '\bcat?s\b' file.txt

B. grep '\bcat?s\b' file.txt

C. grep -E '\bcats?\b' file.txt

D. grep '\bcats?\b' file.txt

Solution

1. Step 1: Understand the pattern needed

   We want to match 'cat' or 'cats'. The 's' is optional, so use s? quantifier.

2. Step 2: Use word boundaries and extended regex

   Use \b for word boundaries and -E to enable ? quantifier.

3. Step 3: Check options

   grep -E '\bcats?\b' file.txt uses grep -E '\bcats?\b' which matches 'cat' or 'cats' correctly. Others either lack -E or misplace the quantifier.

4. Final Answer:

   grep -E '\bcats?\b' file.txt -> Option C

5. Quick Check:

   Use -E and s? to match zero or one s [OK]

Hint: Use -E and s? to match optional s after cat [OK]

Common Mistakes:

• Forgetting -E option for ? quantifier
• Placing ? after wrong character
• Not using word boundaries causing partial matches