FCFS (First Come First Served) in Operating Systems - Time & Space Complexity

Time Complexity: FCFS (First Come First Served)

O(n^2)

Understanding Time Complexity

Analyzing time complexity helps us understand how the FCFS scheduling algorithm performs as the number of processes increases.

We want to know how the work done grows when more processes arrive.

Scenario Under Consideration

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

for each process in process_list:
    wait_time = sum of burst times of all previous processes
    turnaround_time = wait_time + current process burst time
    record wait_time and turnaround_time

This code calculates waiting and turnaround times for each process in the order they arrive.

Identify Repeating Operations

Look at what repeats as the input grows.

• Primary operation: For each process, summing burst times of all previous processes.
• How many times: For each of the n processes, it sums up to n-1 previous burst times.

How Execution Grows With Input

As the number of processes increases, the total work grows faster because each process sums more burst times.

Input Size (n)	Approx. Operations
10	About 55 sums (1+2+...+9)
100	About 4,950 sums
1000	About 499,500 sums

Pattern observation: The total operations grow roughly like the square of the number of processes.

Final Time Complexity

Time Complexity: O(n2)

This means the work needed grows quickly as more processes are added, because each process waits for all before it.

Common Mistake

[X] Wrong: "Calculating waiting times in FCFS is always fast and simple, so it must be O(n)."

[OK] Correct: Because each process's wait time depends on all previous processes, the total work adds up more than just once per process.

Interview Connect

Understanding how FCFS scales helps you explain scheduling choices clearly and shows you can think about how algorithms behave as systems grow.

Self-Check

"What if we stored cumulative burst times as we go instead of summing each time? How would the time complexity change?"