[Solved] Considering Peterson's algorithm, what is the space complexity in terms of the number of processes? - Ans: O(n) due to flag array size growing with processes | Operating Systems

Operating Systems - Critical Section Problem - Requirements & Peterson's Solution

Considering Peterson's algorithm, what is the space complexity in terms of the number of processes?

AO(1) because it uses fixed variables for two processes

BO(n) due to flag array size growing with processes

CO(log n) from hierarchical turn variables

DO(n²) from pairwise turn variables

Step-by-Step Solution

Solution:

Step 1: Understand Peterson's algorithm variables
It uses a flag array and a turn variable.
Step 2: Analyze space for n processes
Flag array size grows linearly with number of processes, so O(n) space.
Step 3: Consider other options
O(1) is only for two processes. O(log n) and O(n²) relate to more complex algorithms, not Peterson's.
Final Answer:
Option B -> Option B
Quick Check:
Flag array size grows linearly with process count [OK]

Quick Trick: Flag array size grows with number of processes [OK]

Common Mistakes:

MISTAKES

Trap Explanation:

PITFALL

Candidates often forget that flags must be maintained per process, leading to underestimating space complexity.

Interviewer Note:

CONTEXT

Master "Critical Section Problem - Requirements & Peterson's Solution" in Operating Systems

2 interactive learning modes - each teaches the same concept differently

More Operating Systems Quizzes

Considering Peterson's algorithm, what is the space complexity in terms of the number of processes?