Time Complexity: du (disk usage by directory)
O(n)
0
0
du (disk usage by directory) in Linux CLI - Time & Space Complexity
Understanding Time Complexity
When using the du command, it is important to understand how its execution time changes as the number of files and directories grows.
We want to know how the command's work increases when the directory size increases.
Scenario Under Consideration
Analyze the time complexity of the following du command usage.
du -sh /path/to/directory
This command calculates the total disk usage of the specified directory and all its contents.
Identify Repeating Operations
Look for repeated actions inside the command's process.
- Primary operation: Traversing each file and subdirectory inside the target directory.
- How many times: Once for every file and folder found inside the directory tree.
How Execution Grows With Input
The command must check every file and folder to calculate sizes, so the work grows as the number of items grows.
| Input Size (n) | Approx. Operations |
|---|---|
| 10 files/folders | About 10 checks |
| 100 files/folders | About 100 checks |
| 1000 files/folders | About 1000 checks |
Pattern observation: The number of operations grows roughly in direct proportion to the number of files and folders.
Final Time Complexity
Time Complexity: O(n)
This means the time taken grows linearly with the number of files and directories inside the target folder.
Common Mistake
[X] Wrong: "The du command only checks the top-level directory, so time stays the same no matter how many files are inside."
[OK] Correct: du actually looks inside every subdirectory and file to sum sizes, so more files mean more work.
Interview Connect
Understanding how commands like du scale helps you reason about performance in real systems and scripts, a useful skill in many automation tasks.
Self-Check
"What if we use du with the --max-depth=1 option? How would the time complexity change?"