SCAN (elevator algorithm) in Operating Systems - Time & Space Complexity

Time Complexity: SCAN (elevator algorithm)

O(n)

Understanding Time Complexity

We want to understand how the SCAN disk scheduling algorithm's running time changes as the number of disk requests grows.

Specifically, how does the number of requests affect the total work done by SCAN?

Scenario Under Consideration

Analyze the time complexity of the following SCAN algorithm snippet.

function SCAN(requests, head, direction) {
  sort requests in ascending order
  while requests remain {
    if direction is up {
      service requests >= head in order
      move head to max request
      direction = down
    } else {
      service requests <= head in reverse order
      move head to min request
      direction = up
    }
  }
}
    

This code moves the disk head back and forth, servicing requests in order along the way.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Traversing the sorted list of requests to service them in order.
• How many times: Each request is visited once during the head's movement in one direction.

How Execution Grows With Input

As the number of requests increases, the algorithm must visit each request once while moving the head back and forth.

Input Size (n)	Approx. Operations
10	About 10 moves to service all requests
100	About 100 moves to service all requests
1000	About 1000 moves to service all requests

Pattern observation: The total work grows roughly in direct proportion to the number of requests.

Final Time Complexity

Time Complexity: O(n)

This means the time to service all requests grows linearly with the number of requests.

Common Mistake

[X] Wrong: "SCAN takes longer than linear time because the head moves back and forth multiple times."

[OK] Correct: Even though the head moves back and forth, each request is only serviced once, so the total work still grows linearly with the number of requests.

Interview Connect

Understanding SCAN's time complexity helps you explain how disk scheduling balances efficiency and fairness, a useful skill in system design discussions.

Self-Check

What if the requests were not sorted before servicing? How would that affect the time complexity?