Page replacement algorithms (FIFO, LRU, Optimal) in Operating Systems - Time & Space Complexity

Time Complexity: Page replacement algorithms (FIFO, LRU, Optimal)

O(n)

Understanding Time Complexity

When a computer runs many programs, it needs to decide which memory pages to keep or replace.

We want to understand how the time to decide and replace pages grows as the number of pages increases.

Scenario Under Consideration

Analyze the time complexity of the FIFO page replacement algorithm.

initialize queue for pages
for each page request in sequence:
    if page in memory:
        continue
    else if memory full:
        remove oldest page from queue
        add new page to queue
    else:
        add new page to queue
    

This code manages pages using a queue to replace the oldest page first when memory is full.

Identify Repeating Operations

Look at what repeats as pages are requested:

• Primary operation: Checking if a page is already in memory (search operation).
• How many times: Once for each page request in the sequence.

How Execution Grows With Input

As the number of page requests grows, the time to check and replace pages grows too.

Input Size (n)	Approx. Operations
10	About 10 checks and possible replacements
100	About 100 checks and possible replacements
1000	About 1000 checks and possible replacements

Pattern observation: The work grows roughly in direct proportion to the number of page requests.

Final Time Complexity

Time Complexity: O(n)

This means the time to handle page requests grows linearly as the number of requests increases.

Common Mistake

[X] Wrong: "Page replacement always takes constant time regardless of memory size."

[OK] Correct: Checking if a page is in memory can take longer if memory holds many pages, so time depends on memory size and request count.

Interview Connect

Understanding how page replacement algorithms scale helps you explain system efficiency clearly and confidently.

Self-Check

What if we changed FIFO to LRU? How would the time complexity change?