Critical section problem in Operating Systems - Time & Space Complexity

Time Complexity: Critical section problem

O(n)

Understanding Time Complexity

We want to understand how the time to manage access to a shared resource changes as more processes try to enter the critical section.

How does the coordination effort grow when more processes compete?

Scenario Under Consideration

Analyze the time complexity of this simplified critical section entry code.

// Pseudocode for n processes
for each process i in 1 to n:
  while (other processes are in critical section):
    wait
  enter critical section
  exit critical section

This code shows how each process waits if another is inside the critical section, ensuring only one process enters at a time.

Identify Repeating Operations

Look at what repeats as more processes try to enter the critical section.

• Primary operation: Checking if other processes are inside the critical section (waiting loop).
• How many times: Each process may wait multiple times depending on how many others are inside or want to enter.

How Execution Grows With Input

As the number of processes increases, the waiting time grows because more processes may be competing to enter.

Input Size (n)	Approx. Operations
10	Processes wait for others, roughly 10 checks per process.
100	Waiting and checking increase, about 100 checks per process.
1000	Waiting grows significantly, around 1000 checks per process.

Pattern observation: The waiting and checking grow roughly in proportion to the number of processes competing.

Final Time Complexity

Time Complexity: O(n)

This means the time spent waiting grows linearly as more processes try to enter the critical section.

Common Mistake

[X] Wrong: "The waiting time stays the same no matter how many processes there are."

[OK] Correct: More processes mean more competition, so waiting and checking increase with the number of processes.

Interview Connect

Understanding how waiting grows with more processes helps you explain synchronization challenges clearly and confidently.

Self-Check

"What if the processes used a more efficient signaling method instead of busy waiting? How would the time complexity change?"