grep (search text patterns) in Linux CLI - Time & Space Complexity

Time Complexity: grep (search text patterns)

O(n)

Understanding Time Complexity

When using grep to search text patterns, it is important to understand how the time it takes grows as the input file gets bigger.

We want to know how the search time changes when the file size increases.

Scenario Under Consideration

Analyze the time complexity of the following grep command.

grep "pattern" filename.txt

This command searches for the word "pattern" in the file named filename.txt and prints matching lines.

Identify Repeating Operations

Look at what grep does internally when searching.

• Primary operation: Checking each line of the file for the pattern.
• How many times: Once for every line in the file, from start to end.

How Execution Grows With Input

As the file gets bigger, grep checks more lines, so the time 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 work grows steadily as the file grows, doubling the file roughly doubles the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to search grows linearly with the size of the file.

Common Mistake

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

[OK] Correct: grep must look at each line to find matches, so bigger files take more time.

Interview Connect

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

Self-Check

What if we searched multiple patterns at once with grep -e? How would the time complexity change?