Time Complexity: which and whereis for commands
O(n)
0
0
which and whereis for commands in Linux CLI - Time & Space Complexity
Understanding Time Complexity
We want to understand how the time it takes to find command locations grows as the system has more commands or files.
How does searching for commands with which and whereis scale when the system gets bigger?
Scenario Under Consideration
Analyze the time complexity of these commands.
which ls
whereis ls
which searches the directories in the PATH to find the executable location. whereis searches standard binary, source, and manual directories for the command.
Identify Repeating Operations
Both commands repeat searches through directories.
- Primary operation: Scanning directories and checking files for the command name.
- How many times: Once per directory in PATH for
which, and multiple standard directories forwhereis.
How Execution Grows With Input
As the number of directories to search grows, the time to find the command grows roughly in proportion.
| Input Size (directories to search) | Approx. Operations |
|---|---|
| 10 | 10 directory checks |
| 100 | 100 directory checks |
| 1000 | 1000 directory checks |
Pattern observation: The time grows linearly as more directories are checked.
Final Time Complexity
Time Complexity: O(n)
This means the time to find a command grows directly with the number of directories searched.
Common Mistake
[X] Wrong: "which and whereis instantly find commands no matter how many directories there are."
[OK] Correct: Both commands must check directories one by one, so more directories mean more work and longer search time.
Interview Connect
Understanding how simple searches scale helps you reason about command lookups and file system operations in real systems.
Self-Check
What if which searched directories in parallel? How would the time complexity change?