Time Complexity: File allocation methods (contiguous, linked, indexed)
O(n)
0
0
File allocation methods (contiguous, linked, indexed) in Operating Systems - Time & Space Complexity
Understanding Time Complexity
When managing files on a disk, the way files are stored affects how long it takes to access them.
We want to understand how the time to find or read a file grows as the file size or disk size increases.
Scenario Under Consideration
Analyze the time complexity of accessing a file using different allocation methods.
// Example: Accessing all blocks of a file
for (int i = 0; i < file_size; i++) {
read_block(block_address[i]);
}
This code reads each block of a file one by one using the block addresses stored according to the allocation method.
Identify Repeating Operations
We look at how many times the system must find and read blocks.
- Primary operation: Reading each block of the file.
- How many times: Once per block, repeated for all blocks in the file.
How Execution Grows With Input
As the file size grows, the number of blocks to read grows too.
| Input Size (blocks) | Approx. Operations (block reads) |
|---|---|
| 10 | 10 reads |
| 100 | 100 reads |
| 1000 | 1000 reads |
Pattern observation: The number of operations grows directly with the file size.
Final Time Complexity
Time Complexity: O(n)
This means the time to access the whole file grows linearly with the number of blocks in the file.
Common Mistake
[X] Wrong: "Accessing any block in a file always takes the same time regardless of allocation method."
[OK] Correct: Different allocation methods affect how quickly the system finds each block, so access time can vary.
Interview Connect
Understanding how file storage methods affect access time helps you explain system design choices clearly and confidently.
Self-Check
What if we used an indexed allocation with a multi-level index? How would that change the time complexity of accessing a block?