Paging concept and page tables in Operating Systems - Time & Space Complexity

Time Complexity: Paging concept and page tables

O(1)

Understanding Time Complexity

When using paging in operating systems, we want to know how the time to find data grows as the memory size increases.

We ask: How does looking up a page in the page table change when the number of pages grows?

Scenario Under Consideration

Analyze the time complexity of the following page table lookup process.

function getPhysicalAddress(virtualAddress) {
  pageNumber = Math.floor(virtualAddress / pageSize);
  offset = virtualAddress % pageSize;
  frameNumber = pageTable[pageNumber];
  physicalAddress = frameNumber * pageSize + offset;
  return physicalAddress;
}
    

This code finds the physical memory address by looking up the page number in the page table and adding the offset.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Accessing the page table array at the index of the page number.
• How many times: Exactly once per address translation.

How Execution Grows With Input

Looking up a page number in the page table takes the same steps no matter how many pages there are.

Input Size (number of pages)	Approx. Operations
10	1 lookup
100	1 lookup
1000	1 lookup

Pattern observation: The time to find a page does not increase as the number of pages grows.

Final Time Complexity

Time Complexity: O(1)

This means the time to translate a virtual address to a physical address stays constant, no matter how big the memory is.

Common Mistake

[X] Wrong: "Looking up a page takes longer as the number of pages grows because the page table gets bigger."

[OK] Correct: The page table is an array, so accessing any page number is done directly by index, which takes the same time regardless of size.

Interview Connect

Understanding that page table lookups are constant time helps you explain how operating systems manage memory efficiently, a key skill in system design discussions.

Self-Check

"What if the page table was implemented as a linked list instead of an array? How would the time complexity change?"