What is the time complexity of implementing LRU page replacement using a hash map and a doubly linked list for n page references and k frames?

medium🪤 Complexity Trap Q5 of Q15

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

AO(n), because each page reference is handled in constant time

BO(n log k), due to searching in a balanced tree structure

CO(nk), because each reference may require scanning all frames

DO(n + k), combining initialization and reference handling

Step-by-Step Solution

Solution:

Step 1: Analyze data structure operations
Hash map provides O(1) lookup, doubly linked list allows O(1) insert/delete. Each of n references handled in O(1), total O(n).
Final Answer:
Option A -> Option A
Quick Check:
Hash + linked list yields O(1) per reference [OK]

Quick Trick: Hash + linked list = O(1) per reference [OK]

Common Mistakes:

MISTAKES

Trap Explanation:

PITFALL

Candidates often think scanning frames is needed, missing the O(1) update via hash and linked list.

Interviewer Note:

CONTEXT

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

More Operating Systems Quizzes