0

Which statement correctly describes the space complexity of the Optimal page replacement algorithm when implemented for a reference string of length n and k frames?

medium🪤 Complexity Trap Q6 of Q15

Operating Systems - Page Replacement - FIFO, LRU, Optimal Algorithm

Which statement correctly describes the space complexity of the Optimal page replacement algorithm when implemented for a reference string of length n and k frames?

AO(n), because future references must be stored or scanned

BO(k), since only current frames are stored

CO(nk), due to tracking all pages in all frames over time

DO(1), as it only needs to know the next page to replace

Step-by-Step Solution

Solution:

Step 1: Understand Optimal algorithm requirements
Optimal requires knowledge of future references, so it must store or access the entire reference string of length n, leading to O(n) space.
Final Answer:
Option A -> Option A
Quick Check:
Future knowledge requires O(n) space [OK]

Quick Trick: Optimal needs full future reference info, O(n) space [OK]

Common Mistakes:

MISTAKES

Assuming only current frames stored (O(k))
Thinking O(1) suffices for future knowledge
Confusing time and space complexity

Trap Explanation:

PITFALL

Candidates underestimate space needed to store or scan future references for Optimal.

Interviewer Note:

CONTEXT

Tests understanding of Optimal algorithm's practical resource needs.

Master "Page Replacement - FIFO, LRU, Optimal Algorithm" in Operating Systems

2 interactive learning modes - each teaches the same concept differently

Want More Practice?

15+ quiz questions · All difficulty levels · Free

Free Signup - Practice All Questions

More Operating Systems Quizzes