FCFS disk scheduling in Operating Systems - Time & Space Complexity

Time Complexity: FCFS disk scheduling

O(n)

Understanding Time Complexity

We want to understand how the time to complete disk requests grows as more requests come in when using FCFS disk scheduling.

Specifically, how does the number of disk movements increase with the number of requests?

Scenario Under Consideration

Analyze the time complexity of the following FCFS disk scheduling code snippet.

int total_movement = 0;
int current_position = start_position;
for (int i = 0; i < n; i++) {
    total_movement += abs(requests[i] - current_position);
    current_position = requests[i];
}
return total_movement;
    

This code calculates the total head movement by servicing disk requests in the order they arrive.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through each disk request once.
• How many times: Exactly once per request, so n times.

How Execution Grows With Input

As the number of requests increases, the total operations grow directly with the number of requests.

Input Size (n)	Approx. Operations
10	10 operations
100	100 operations
1000	1000 operations

Pattern observation: The work grows in a straight line with the number of requests.

Final Time Complexity

Time Complexity: O(n)

This means the time to process all requests grows directly in proportion to how many requests there are.

Common Mistake

[X] Wrong: "The time depends on how far the disk head moves, so it could be more than linear."

[OK] Correct: While the total movement distance varies, the number of steps in the code is always one per request, so time complexity is based on request count, not distance.

Interview Connect

Understanding how FCFS disk scheduling scales helps you explain simple scheduling algorithms clearly and shows you can analyze how work grows with input size.

Self-Check

"What if we changed FCFS to a scheduling algorithm that sorts requests before processing? How would the time complexity change?"