Sign inSign in
ConceptSystems & CS

LRU lemma

A theorem stating that an algorithm incurring Q misses on an ideal cache of size M will incur at most 2Q misses on a fully associative cache of size 2M using the least-recently used replacement policy.
Watch it explained

Know first

Named as a prerequisite by the lectures that define this. The number is how many say so. A grey one has no page yet.

Cache1Cache miss1Fully associative cache1Ideal-cache model1Least-recently used (LRU) replacement1Least-recently used replacement policy1

Lecturers

1

    Connections

    5

    The lectures that define it or assume it, and the concepts next to it.

    Concepts4

    Lecture1

    1 lecturer. Definitions are written by AI from each lecture’s transcript. A time with a play mark starts the lecture at the moment the lecturer says it.