The theoretically optimal page replacement algorithm (Offline Page Replacements)

From Algorithm Wiki
Revision as of 11:17, 15 February 2023 by Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(k)$ words (Need to keep track of cache; linear scan for searching for page not being used for the longest only requires O(1) auxiliary space) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

Time Complexity

$O(n^{2})$

Space Complexity

$O(k)$ words

(Need to keep track of cache; linear scan for searching for page not being used for the longest only requires O(1) auxiliary space)

Description

Approximate?

Exact

Randomized?

No, deterministic

Model of Computation

Word RAM

Year

1940

Reference

Retrieved from "https://algorithm-wiki-csail-mit-edu.ezproxy.canberra.edu.au/w/index.php?title=The_theoretically_optimal_page_replacement_algorithm_(Offline_Page_Replacements)&oldid=45596"