Operating Systems - File Allocation Methods - Contiguous, Linked, Indexed
What is the time complexity of accessing the nth block in a file stored using linked allocation, and why might candidates mistakenly think it is O(1)?
What is the time complexity of accessing the nth block in a file stored using linked allocation, and why might candidates mistakenly think it is O(1)?
medium🪤 Complexity Trap Q5 of Q15
Step-by-Step Solution
Solution:
Step 1: Recall linked allocation access
Accessing nth block requires following n-1 pointers sequentially.Step 2: Understand why O(n)
Each pointer traversal is constant time, but total is linear in n.Step 3: Address misconception
Candidates may think pointers imply direct access, confusing linked with indexed allocation.Step 4: Evaluate other options
O(1) is incorrect; O(log n) and O(n^2) do not apply to simple linked lists.Final Answer:
Option B -> Option BQuick Check:
Sequential pointer traversal -> O(n) access time [OK]
Quick Trick: Linked allocation access is linear, not constant time [OK]
Common Mistakes:
MISTAKES- Assuming direct pointers to all blocks exist
- Confusing linked allocation with indexed allocation
- Overestimating complexity to O(n^2)
Trap Explanation:
PITFALL- Candidates often overlook sequential pointer traversal cost, assuming direct access.
Interviewer Note:
CONTEXT- Tests understanding of access time complexity and common misconceptions in linked allocation.
Master "File Allocation Methods - Contiguous, Linked, Indexed" in Operating Systems
Want More Practice?
15+ quiz questions · All difficulty levels · Free
Free Signup - Practice All QuestionsMore Operating Systems Quizzes