Time Complexity: mv (move and rename)
O(1)
0
0
mv (move and rename) in Linux CLI - Time & Space Complexity
Understanding Time Complexity
When using the mv command to move or rename files/directories, it's helpful to understand how the time it takes grows as the number of files or size changes.
We want to know how the command's work changes when moving one file versus many files in a folder. Key factor: whether source and destination are on the same filesystem.
Scenario Under Consideration
Analyze the time complexity of the following mv command usage (assuming same filesystem).
mv source.txt destination.txt
mv folder1/ folder2/This moves or renames a single file or an entire folder to a new location or name.
Identify Repeating Operations
Look at what the command does repeatedly.
- Primary operation: Single
rename(2)system call to update directory entry. - How many times: Once, regardless of the number of files inside directories.
Note: mv uses rename() if source and dest are on the same filesystem (fast). Otherwise, it copies all contents (slow, O(n)).
How Execution Grows With Input
As the number of files grows, the work stays constant (for same filesystem).
| Input Size (n) | Approx. Operations |
|---|---|
| 10 files | 1 rename operation |
| 100 files | 1 rename operation |
| 1000 files | 1 rename operation |
Pattern observation: The time is constant, independent of the number of files (same filesystem).
Final Time Complexity
Time Complexity (same filesystem): O(1)
Time Complexity (different filesystems): O(n) where n is total data size.
This means the time is constant for typical same-disk moves.
Common Mistake
[X] Wrong: "Moving a folder always takes time proportional to the number/size of files inside."
[OK] Correct: On the same filesystem, mv just updates the parent directory's entry (atomic rename), independent of contents.
Interview Connect
Understanding mv's behavior (O(1) vs O(n)) shows knowledge of filesystems, syscalls, and efficiency in scripting/automation.
Self-Check
What if we moved files across different disks instead of within the same disk? How would the time complexity change?
Answer: Becomes O(n) as it recursively copies all contents then deletes source.