Pipe operator (|) in Linux CLI - Time & Space Complexity

Time Complexity: Pipe operator (|)

O(n + m log m)

Understanding Time Complexity

When using the pipe operator (|) in Linux commands, it's important to understand how the time to run commands grows as input size increases.

We want to know how the total work changes when commands are connected by pipes.

Scenario Under Consideration

Analyze the time complexity of the following command pipeline.

cat file.txt | grep "error" | sort | uniq

This pipeline reads a file, filters lines containing "error", sorts them, and removes duplicates.

Identify Repeating Operations

Look at the repeated work done by each command in the pipeline.

• Primary operation: Most commands process lines from the input one by one, but sort collects and sorts them.
• How many times: Each line passes through all commands sequentially.

How Execution Grows With Input

As the number of lines (n) grows, cat and grep process O(n) lines, sort takes O(m log m) time where m is the number of lines containing "error", and uniq O(m), so total work is O(n + m log m).

Input Size (n)	Approx. Operations
10	Processes about 10 lines through cat and grep; sorts and uniq on fewer lines
100	Processes about 100 lines through cat and grep; sorts and uniq on fewer lines
1000	Processes about 1000 lines through cat and grep; sorts and uniq on fewer lines

Pattern observation: The total work grows roughly as O(n + m log m), where m ≤ n.

Final Time Complexity

Time Complexity: O(n + m log m)

This means the total time grows linearly with input size n for cat and grep, and as m log m for sorting the filtered lines.

Common Mistake

[X] Wrong: "Using pipes makes the commands run faster and reduces total work."

[OK] Correct: Pipes connect commands but each command still processes all input lines it receives, so total work adds up rather than shrinks.

Interview Connect

Understanding how pipelines scale helps you write efficient scripts and explain your reasoning clearly in real situations.

Self-Check

What if we replaced the sort command with a command that only looks at the first 10 lines? How would the time complexity change?