Time Complexity: stdin redirection (<)
O(n log n)
0
0
stdin redirection (<) in Linux CLI - Time & Space Complexity
Understanding Time Complexity
We want to understand how the time taken by a command changes when we use stdin redirection.
Specifically, how does reading input from a file affect execution time as the file size grows?
Scenario Under Consideration
Analyze the time complexity of the following command using stdin redirection.
sort < input.txt
This command sorts lines from the file input.txt by reading it through stdin redirection.
Identify Repeating Operations
Look at what repeats as the input grows.
- Primary operation: Reading each line from the input file and sorting all lines.
- How many times: Once for each line in the file, plus sorting steps that depend on total lines.
How Execution Grows With Input
As the file gets bigger, the command reads more lines and sorting takes longer.
| Input Size (n lines) | Approx. Operations |
|---|---|
| 10 | Reads 10 lines, sorts 10 lines |
| 100 | Reads 100 lines, sorts 100 lines |
| 1000 | Reads 1000 lines, sorts 1000 lines |
Pattern observation: Reading grows linearly, sorting grows faster than linear as input grows.
Final Time Complexity
Time Complexity: O(n log n)
This means the time grows a bit faster than the number of lines because sorting takes more steps as input grows.
Common Mistake
[X] Wrong: "Reading input with < is instant and does not affect time."
[OK] Correct: Reading input still takes time proportional to file size, so bigger files take longer to read before sorting.
Interview Connect
Understanding how input size affects command time helps you reason about script performance and efficiency in real tasks.
Self-Check
What if we replaced sort < input.txt with sort input.txt? How would the time complexity change?