Operating Systems - Critical Section Problem - Requirements & Peterson's Solution
What is the time complexity of Peterson's algorithm in terms of the number of processes entering the critical section?
What is the time complexity of Peterson's algorithm in terms of the number of processes entering the critical section?
medium🪤 Complexity Trap Q5 of Q15
Step-by-Step Solution
Solution:
Step 1: Recall Peterson's algorithm scope
It is designed for exactly two processes.Step 2: Analyze complexity per entry
Since only two processes are involved, the time to enter critical section is constant, O(1).Step 3: Consider other options
O(n) and O(log n) relate to algorithms supporting multiple processes, which Peterson's does not. O(n²) is incorrect as no nested loops exist.Final Answer:
Option C -> Option CQuick Check:
Peterson's algorithm is constant time for two processes [OK]
Quick Trick: Peterson's algorithm is for two processes only, so O(1) time [OK]
Common Mistakes:
MISTAKES- Assuming it scales to n processes
- Confusing complexity with multi-process algorithms
Trap Explanation:
PITFALL- Candidates often overgeneralize Peterson's algorithm to multiple processes, leading to wrong complexity assumptions.
Interviewer Note:
CONTEXT- Tests understanding of algorithm scope and complexity implications.
Master "Critical Section Problem - Requirements & Peterson's Solution" in Operating Systems
Want More Practice?
15+ quiz questions · All difficulty levels · Free
Free Signup - Practice All QuestionsMore Operating Systems Quizzes