What is the time complexity of address translation in a pure paging system without any hardware support like TLB?

medium🪤 Complexity Trap Q5 of Q15

Operating Systems - Paging vs Segmentation - Address Translation

AO(1), because page number directly indexes the page table

BO(log n), if the page table is implemented as a balanced tree

CO(n), where n is the number of pages, because the page table must be searched linearly

DO(n^2), due to nested page table lookups

Step-by-Step Solution

Solution:

Step 1: Understand page table lookup
In pure paging without hardware support, the page table is typically a simple array indexed by the page number.
Step 2: Consider access time
Each lookup requires a memory access to the page table entry, which is O(1) time complexity.
Step 3: Evaluate options
O(1), because page number directly indexes the page table is correct. O(log n), if the page table is implemented as a balanced tree is invalid as page tables are not balanced trees. O(n), where n is the number of pages, because the page table must be searched linearly is incorrect; page tables are indexed arrays, not searched linearly. O(n^2), due to nested page table lookups is wrong; no nested lookups in pure paging.
Final Answer:
Option A -> Option B
Quick Check:
Page table lookup by direct indexing is O(1) [OK]

Quick Trick: Page table lookup by direct indexing is O(1) [OK]

Common Mistakes:

MISTAKES

Trap Explanation:

PITFALL

Candidates often assume linear search due to memory access delays, but page tables are indexed arrays allowing O(1) access.

Interviewer Note:

CONTEXT

Tests understanding of practical complexity of paging without hardware acceleration

Master "Paging vs Segmentation - Address Translation" 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