grep -r for recursive search in Linux CLI - Time & Space Complexity

Time Complexity: grep -r for recursive search

O(n)

Understanding Time Complexity

When using grep -r, we search through many files inside folders and subfolders. Understanding how the time it takes grows helps us know what to expect when searching large directories.

We want to know how the search time changes as the number of files and their sizes increase.

Scenario Under Consideration

Analyze the time complexity of the following command.

grep -r "pattern" /path/to/directory

This command searches recursively for the word "pattern" inside all files under the given directory and its subdirectories.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Reading each file line by line to check for the pattern.
• How many times: Once for every line in every file under the directory and its subdirectories.

How Execution Grows With Input

As the number of files and their sizes grow, the total lines to check increase, making the search take longer.

Input Size (n = total 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 direct proportion to the total number of lines searched.

Final Time Complexity

Time Complexity: O(n)

This means the search time grows linearly with the total number of lines in all files searched.

Common Mistake

[X] Wrong: "The search time depends only on the number of files, not their size."

[OK] Correct: Even a single large file with many lines takes longer to search than many small files combined. The total lines matter most.

Interview Connect

Knowing how recursive search scales helps you understand real-world command efficiency. It shows you can think about how tools behave with growing data, a useful skill in scripting and automation.

Self-Check

"What if we used grep -r --exclude-dir=logs to skip some folders? How would that affect the time complexity?"