Time Complexity: fdisk and lsblk
O(n)
0
0
fdisk and lsblk in Linux CLI - Time & Space Complexity
Understanding Time Complexity
When using commands like fdisk and lsblk, it helps to understand how their execution time changes as the number of disks or partitions grows.
We want to know how the time to list or manage disks grows when there are more devices or partitions.
Scenario Under Consideration
Analyze the time complexity of the following commands.
lsblk
fdisk -l
lsblk lists all block devices and their partitions. fdisk -l lists detailed partition info for all disks.
Identify Repeating Operations
Both commands scan devices and partitions one by one.
- Primary operation: Reading info for each disk and its partitions.
- How many times: Once per disk and once per partition inside each disk.
How Execution Grows With Input
As the number of disks and partitions grows, the commands take longer because they check each item.
| Input Size (number of disks + partitions) | Approx. Operations |
|---|---|
| 10 | About 10 device reads |
| 100 | About 100 device reads |
| 1000 | About 1000 device reads |
Pattern observation: The time grows roughly in direct proportion to the number of devices and partitions.
Final Time Complexity
Time Complexity: O(n)
This means the time to run these commands grows linearly with the number of disks and partitions.
Common Mistake
[X] Wrong: "These commands run instantly no matter how many disks there are."
[OK] Correct: The commands must check each disk and partition, so more devices mean more work and longer time.
Interview Connect
Understanding how command execution time grows with input size helps you reason about system performance and scripting efficiency in real tasks.
Self-Check
What if we only list partitions on a single disk instead of all disks? How would the time complexity change?