What is the time complexity of servicing N disk requests using SSTF, and why might it be inefficient for large N?

medium🪤 Complexity Trap Q5 of Q15

Operating Systems - Disk Scheduling - SSTF, SCAN, C-SCAN

AO(N log N), because requests are sorted once and then serviced sequentially

BO(N^2), because each selection requires scanning all remaining requests to find the closest

CO(N), because SSTF always picks the next closest request in constant time

DO(log N), because a priority queue is used to select the closest request

Step-by-Step Solution

Solution:

Step 1: Analyze SSTF selection process
For each of the N requests, SSTF scans all remaining requests to find the closest.
Step 2: Calculate total operations
First selection scans N requests, second scans N-1, and so on, totaling O(N^2).
Step 3: Consider data structures
Without advanced data structures, SSTF cannot achieve better than O(N^2).
Final Answer:
Option B -> Option B
Quick Check:
Repeated scanning leads to quadratic time [OK]

Quick Trick: SSTF scans all remaining requests each time -> O(N^2) [OK]

Common Mistakes:

MISTAKES

Trap Explanation:

PITFALL

Candidates often assume SSTF can be done in O(N log N) by sorting, ignoring dynamic closest selection.

Interviewer Note:

CONTEXT

Master "Disk Scheduling - SSTF, SCAN, C-SCAN" in Operating Systems

2 interactive learning modes - each teaches the same concept differently

Want More Practice?

15+ quiz questions · All difficulty levels · Free

More Operating Systems Quizzes