du (disk usage by directory) in Linux CLI - Time & Space Complexity

Time Complexity: du (disk usage by directory)

O(n)

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?"

Practice

1. What does the du command primarily show in Linux?

easy

A. The disk space used by files and directories

B. The number of files in a directory

C. The current directory path

D. The list of running processes

Solution

1. Step 1: Understand the purpose of du

   The du command stands for disk usage and shows how much space files and directories use.

2. Step 2: Compare options

   Options B, C, and D relate to other commands like ls or ps, not du.

3. Final Answer:

   The disk space used by files and directories -> Option A

4. Quick Check:

   du = disk space used [OK]

Hint: Remember: du = disk usage, shows space used [OK]

Common Mistakes:

• Confusing du with ls or ps commands
• Thinking du shows file counts
• Assuming du shows current directory path

2. Which du command option shows sizes in a human-readable format?

easy

A. -s

B. -c

C. -a

D. -h

Solution

1. Step 1: Identify the option for human-readable sizes

   The -h option makes sizes easier to read by adding units like K, M, G.

2. Step 2: Understand other options

   -s summarizes, -a shows all files, -c adds a total line.

3. Final Answer:

   -h -> Option D

4. Quick Check:

   -h = human-readable sizes [OK]

Hint: Use -h for sizes like KB, MB, GB [OK]

Common Mistakes:

• Using -s expecting human-readable sizes
• Confusing -a or -c with size formatting
• Omitting the -h option for readability

3. What is the output of the command du -sh /var/log if the /var/log directory uses 120M of disk space?

medium

A. 120M

B. 120M /var/log

C. 120MB /var/log

D. 120 /var/log

Solution

1. Step 1: Understand the command options

   -s summarizes total size, -h shows human-readable format.

2. Step 2: Predict output format

   The output shows size with unit, a tab, then directory path: "120M\t/var/log".

3. Final Answer:

   120M /var/log -> Option B

4. Quick Check:

   du -sh output = size + tab + path [OK]

Hint: du -sh shows size and path separated by tab [OK]

Common Mistakes:

• Omitting the tab separator
• Writing size without unit
• Showing size without path

4. You run du -h /home/user but get an error: "du: invalid option -- 'h'". What is the likely cause?

medium

A. The directory /home/user does not exist

B. You need to run the command as root

C. The du command does not support the -h option on this system

D. You must use --human-readable instead of -h

Solution

1. Step 1: Analyze the error message

   The error says -h is invalid, meaning this du version lacks that option.

2. Step 2: Check other options

   Running as root or directory existence wouldn't cause invalid option error; -h is standard, no need for long form.

3. Final Answer:

   The du command does not support the -h option on this system -> Option C

4. Quick Check:

   Invalid option error means unsupported flag [OK]

Hint: Invalid option means your du version lacks that flag [OK]

Common Mistakes:

• Assuming permission or path errors cause invalid option
• Trying --human-readable instead of checking version
• Ignoring error message details

5. You want to find the total disk usage of all subdirectories inside /home/user but only see sizes for individual files. Which command correctly summarizes each subdirectory size in human-readable form?

hard

A. du -sh /home/user/*

B. du -ah /home/user

C. du -h /home/user

D. du -s /home/user

Solution

1. Step 1: Understand the goal

   You want sizes of each subdirectory summarized, not individual files.

2. Step 2: Analyze options

   du -ah shows all files and dirs, du -sh on directory alone summarizes total only, du -s no human-readable. du -sh /home/user/* summarizes each subdirectory separately in human-readable form.

3. Final Answer:

   du -sh /home/user/* -> Option A

4. Quick Check:

   Use du -sh with wildcard for each subdir [OK]

Hint: Use du -sh with * to summarize each subdirectory [OK]

Common Mistakes:

• Using -a to include files instead of just dirs
• Using -s alone for total only
• Not using wildcard to list subdirectories