SSTF (Shortest Seek Time First) in Operating Systems - Time & Space Complexity

Time Complexity: SSTF (Shortest Seek Time First)

O(n)

Understanding Time Complexity

Analyzing time complexity helps us understand how the SSTF disk scheduling algorithm performs as the number of disk requests grows.

We want to know how the time to select the next request changes when there are more requests waiting.

Scenario Under Consideration

Analyze the time complexity of the following SSTF selection process.

function selectNextRequest(currentPosition, requests) {
  let shortestDistance = Infinity;
  let nextRequest = null;
  for (let i = 0; i < requests.length; i++) {
    let distance = Math.abs(requests[i] - currentPosition);
    if (distance < shortestDistance) {
      shortestDistance = distance;
      nextRequest = requests[i];
    }
  }
  return nextRequest;
}
    

This code finds the disk request closest to the current head position by checking all pending requests.

Identify Repeating Operations

Look for repeated actions that take time.

• Primary operation: Loop through all disk requests to find the closest one.
• How many times: Once per selection, looping over all requests (n times).

How Execution Grows With Input

As the number of requests increases, the time to find the closest request grows proportionally.

Input Size (n)	Approx. Operations
10	About 10 checks
100	About 100 checks
1000	About 1000 checks

Pattern observation: The number of operations grows directly with the number of requests.

Final Time Complexity

Time Complexity: O(n)

This means the time to pick the next request grows linearly as more requests are waiting.

Common Mistake

[X] Wrong: "SSTF instantly finds the closest request regardless of how many requests there are."

[OK] Correct: SSTF must check each request to find the closest one, so more requests mean more work.

Interview Connect

Understanding how SSTF scales helps you explain disk scheduling choices clearly and shows you can analyze algorithm efficiency in real systems.

Self-Check

"What if the requests were kept sorted by position? How would that affect the time complexity of finding the next request?"