C-SCAN (circular SCAN) in Operating Systems - Time & Space Complexity

Time Complexity: C-SCAN (circular SCAN)

O(n log n)

Understanding Time Complexity

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

We want to know how the total work changes when more requests arrive.

Scenario Under Consideration

Analyze the time complexity of the following C-SCAN scheduling process.

function cscan(requests, head, disk_size) {
  requests.sort()
  let total_movement = 0
  let index = 0;
  while (index < requests.length && requests[index] < head) {
    index++;
  }

  for (let i = index; i < requests.length; i++) {
    total_movement += Math.abs(requests[i] - head)
    head = requests[i]
  }

  total_movement += Math.abs(disk_size - 1 - head) + (disk_size - 1)
  head = 0

  for (let i = 0; i < index; i++) {
    total_movement += Math.abs(requests[i] - head)
    head = requests[i]
  }

  return total_movement
}
    

This code moves the disk head from its current position to the end, then jumps to the start, and services all requests in a circular manner.

Identify Repeating Operations

Look for loops or repeated steps that process requests.

• Primary operation: Two loops each scanning part of the sorted request list.
• How many times: Each request is visited exactly once in total.

How Execution Grows With Input

As the number of requests increases, the algorithm processes each request once in order.

Input Size (n)	Approx. Operations
10	About 10 steps to move and service requests
100	About 100 steps
1000	About 1000 steps

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

Final Time Complexity

Time Complexity: O(n log n)

This means the time grows a bit faster than the number of requests because sorting is needed, but each request is only handled once.

Common Mistake

[X] Wrong: "The C-SCAN algorithm runs in linear time because it just moves through requests once."

[OK] Correct: Sorting the requests first takes extra time, which grows faster than just scanning, so the total time is not purely linear.

Interview Connect

Understanding how C-SCAN scales helps you explain disk scheduling efficiency clearly, showing you grasp both algorithm steps and their cost.

Self-Check

"What if the requests were already sorted? How would that affect the time complexity of C-SCAN?"