Complexity of an LRU Cache

The hash map plus doubly linked list design makes every operation constant time on average. This chapter explains where that bound comes from, what it costs in memory, how simpler designs compare, and why hit ratio matters as much as Big-O.

Time per operation

The list operations are O(1) in the worst case because each changes at most four pointers. The hash map is O(1) on average; with pathological collisions a lookup can degrade to O(n), and resizing makes insertion amortized rather than strictly constant. In practice, with a decent hash function, every operation is a handful of memory accesses.

Space

The cache holds at most capacity entries, so space is O(capacity). The constant factor is larger than for a plain dict: each entry needs a map slot, a node object, two pointers and a second reference to the key. You can see the overhead in Python:

import sys

class Node:
    __slots__ = ("key", "value", "prev", "next")

class FatNode:
    def __init__(self):
        self.key = self.value = self.prev = self.next = None

slim, fat = Node(), FatNode()
print(sys.getsizeof(slim))                            # e.g. 64 bytes
print(sys.getsizeof(fat) + sys.getsizeof(fat.__dict__))  # noticeably more

Exact numbers depend on the Python version, but __slots__ consistently saves memory per node. OrderedDict and functools.lru_cache keep their links in C, which is cheaper still.

Why simpler designs are slower

Many first attempts keep keys in a plain list and move them around. Finding and removing a key in a Python list costs O(n), so each operation becomes linear.

class NaiveLRU:
    def __init__(self, capacity):
        self.capacity = capacity
        self.order = []          # least recent first
        self.data = {}

    def get(self, key):
        if key not in self.data:
            return None
        self.order.remove(key)   # O(n) search and shift
        self.order.append(key)
        return self.data[key]

    def put(self, key, value):
        if key in self.data:
            self.order.remove(key)
        elif len(self.data) >= self.capacity:
            del self.data[self.order.pop(0)]  # O(n) shift
        self.order.append(key)
        self.data[key] = value

A small benchmark makes the difference visible as the capacity grows.

import random
import timeit
from collections import OrderedDict

def ordered_ops(capacity, keys):
    cache = OrderedDict()
    for k in keys:
        if k in cache:
            cache.move_to_end(k)
        else:
            cache[k] = k
            if len(cache) > capacity:
                cache.popitem(last=False)

def naive_ops(capacity, keys):
    order, data = [], set()
    for k in keys:
        if k in data:
            order.remove(k)
        elif len(order) >= capacity:
            data.discard(order.pop(0))
        order.append(k)
        data.add(k)

keys = [random.randrange(4000) for _ in range(20000)]
for name, fn in [("OrderedDict", ordered_ops), ("list", naive_ops)]:
    seconds = timeit.timeit(lambda: fn(2000, keys), number=1)
    print(f"{name:12} {seconds:.3f}s")

Comparison with other policies

CLOCK and sampled LRU exist because true LRU updates shared pointers on every read, which is expensive for hardware and for highly concurrent software. They give up exact recency order in exchange for cheaper hits.

Hit ratio matters more than Big-O

All good designs are O(1); what differs in practice is the hit ratio. A useful property of LRU is that it is a stack algorithm: for the same request sequence, a larger LRU cache never has more misses than a smaller one. FIFO does not have this property (Belady's anomaly). Measure the hit ratio on a realistic workload before choosing a capacity.

Summary

• get and put are O(1) on average; the list part is O(1) in the worst case.
• Space is O(capacity) with a per-entry overhead for nodes and pointers.
• List-based or scan-based designs are O(n); heap-based designs are O(log n).
• Choose capacity and policy by measured hit ratio, not only by complexity.