Basic regex in grep in Bash Scripting - Time & Space Complexity

Time Complexity: Basic regex in grep

O(n)

Understanding Time Complexity

We want to understand how the time it takes to search text with grep grows as the input size grows.

Specifically, how does grep's use of basic regular expressions affect the time it takes to find matches?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

grep "pattern" largefile.txt

This command searches for lines matching "pattern" in a large text file.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: grep reads each line of the file and checks if it matches the pattern.
• How many times: Once for every line in the file, so the number of lines is the main factor.

How Execution Grows With Input

As the file gets bigger, grep checks more lines, so the work grows roughly in direct proportion to the number of lines.

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

Pattern observation: The time grows roughly in a straight line as the number of lines increases.

Final Time Complexity

Time Complexity: O(n)

This means the time grep takes grows directly with the number of lines it checks.

Common Mistake

[X] Wrong: "grep runs instantly no matter how big the file is."

[OK] Correct: grep must check each line, so bigger files take more time.

Interview Connect

Understanding how tools like grep scale helps you reason about performance in real scripts and automation tasks.

Self-Check

"What if we used grep with a more complex regex that backtracks a lot? How would the time complexity change?"

Practice

1. What does the caret symbol ^ mean in a basic regex pattern used with grep?

easy

A. It matches the end of a line

B. It matches the start of a line

C. It matches any single character

D. It matches zero or more repetitions

Solution

1. Step 1: Understand caret usage in regex

   The caret ^ is used to anchor the pattern to the start of a line in basic regex.

2. Step 2: Compare with other anchors

   The dollar sign $ matches the end of a line, so caret is specifically for the start.

3. Final Answer:

   It matches the start of a line -> Option B

4. Quick Check:

   ^ means start of line [OK]

Hint: Caret (^) always means line start in grep regex [OK]

Common Mistakes:

• Confusing ^ with $ (end of line)
• Thinking ^ matches any character
• Using ^ to mean OR condition

2. Which of the following is the correct basic regex syntax to search for lines containing either "cat" or "dog" using grep?

easy

A. grep 'cat\|dog' file.txt

B. grep 'cat|dog' file.txt

C. grep 'cat\dog' file.txt

D. grep 'cat/dog' file.txt

Solution

1. Step 1: Understand OR in basic regex

   In basic regex with grep, the OR operator is written as \|, not just |.

2. Step 2: Check each option

   grep 'cat|dog' file.txt uses | without escape, which is invalid in basic regex. grep 'cat\|dog' file.txt correctly escapes it as \|. Options C and D use wrong characters.

3. Final Answer:

   grep 'cat\|dog' file.txt -> Option A

4. Quick Check:

   OR in basic grep regex = \| [OK]

Hint: Use \| for OR in basic grep regex [OK]

Common Mistakes:

• Using | without escaping in basic grep
• Confusing \| with \dog or /
• Forgetting to escape special characters

3. Given a file animals.txt with these lines:

cat
caterpillar
dog
catalog
dogma

What is the output of grep '^cat$' animals.txt?

medium

A. cat
caterpillar
catalog

B. caterpillar
catalog

C. cat

D. No output

Solution

1. Step 1: Understand the regex pattern

   The pattern ^cat$ matches lines that start and end exactly with "cat" (no extra characters).

2. Step 2: Check each line against pattern

   Only the line "cat" matches exactly. "caterpillar" and "catalog" have extra characters, so they don't match.

3. Final Answer:

   cat -> Option C

4. Quick Check:

   ^cat$ matches exact line 'cat' [OK]

Hint: Use ^ and $ to match exact whole line [OK]

Common Mistakes:

• Assuming partial matches with ^ and $
• Ignoring line boundaries in regex
• Confusing grep default substring match with anchored match

4. You want to find lines containing either "apple" or "banana" in fruits.txt using basic regex with grep. Which command uses incorrect syntax for the OR operation?

medium

A. grep 'apple|banana' fruits.txt

B. grep 'apple\|banana$' fruits.txt

C. grep '^apple\|banana$' fruits.txt

D. grep 'apple\|banana' fruits.txt

Solution

1. Step 1: Identify correct OR syntax in basic grep

   Basic regex requires escaping the OR operator as \|. Using | alone treats it as a literal | character, not as an OR operator.

2. Step 2: Check each option

   grep 'apple|banana' fruits.txt uses | without escape, treating | as literal, not OR. Options A, B, and C correctly escape OR operator.

3. Final Answer:

   grep 'apple|banana' fruits.txt -> Option A

4. Quick Check:

   Unescaped | in basic grep regex = literal |, not OR [OK]

Hint: Escape | as \| in basic grep regex [OK]

Common Mistakes:

• Not escaping | in basic regex
• Mixing extended regex syntax without -E flag
• Misplacing anchors with OR operator

5. You want to find lines in data.txt that start with "error" or end with "fail" using basic regex with grep. Which command correctly does this?

hard

A. grep '^error\|fail' data.txt

B. grep '^error|fail$' data.txt

C. grep '^error$\|fail$' data.txt

D. grep '^error\|fail$' data.txt

Solution

1. Step 1: Understand the pattern requirements

   We want lines starting with "error" OR lines ending with "fail". So pattern is ^error OR fail$.

2. Step 2: Use correct OR syntax in basic regex

   Basic regex OR is \|. So pattern is ^error\|fail$. grep '^error\|fail$' data.txt matches this exactly.

3. Step 3: Check other options

   grep '^error|fail$' data.txt misses escape on OR, causing error. grep '^error$\|fail$' data.txt incorrectly anchors "error" with $. grep '^error\|fail' data.txt misses anchor on "fail".

4. Final Answer:

   grep '^error\|fail$' data.txt -> Option D

5. Quick Check:

   Start with ^error OR end with fail$ using \| [OK]

Hint: Combine ^ and $ with \| for OR in basic grep regex [OK]

Common Mistakes:

• Not escaping | in basic regex
• Misplacing anchors with OR operator
• Using $ with start anchor or vice versa