LRU Cache: O(1) Operations Explained

Hello! Let's dive back into our study of core data structures.

In the previous lesson, we successfully implemented a production-quality, thread-safe LRU cache by combining a hash map with our custom doubly linked list. We focused on making it robust for concurrent access, a critical requirement for services like the ones you engineer at AWS.

Today, we shift our focus from implementation to analysis. The entire justification for using this complex design rests on one critical promise: constant-time performance. This lesson is dedicated to proving that promise. We will meticulously justify the O(1) time complexity of the get and put operations in our from-scratch LRU Cache.

In a technical interview, stating that an LRU cache is O(1) is expected. Being able to break it down and prove it step-by-step is what distinguishes a strong candidate.

1. The Foundation for O(1) Performance

Before we analyze the operations, let's briefly recap why the combination of a hash map and a doubly linked list is so effective. Any other choice leads to a performance bottleneck.

• A hash map (dict) alone gives us O(1) lookups but provides no mechanism to track the usage order of items.
• A linked list alone maintains order, but finding an item requires traversing the list, an O(N) operation.

The following video segment lucidly explains why a linked list by itself is insufficient and fails the O(1) requirement.

This brings us to our chosen architecture:

1. Hash Map (dict): Provides O(1) average time for get, set, and delete operations. We use it to map a key to a direct reference to a node in our linked list.
2. Doubly Linked List (DoublyLinkedList): Provides O(1) time for adding/removing nodes from either end, and critically, O(1) time to remove an arbitrary node if you already have a pointer to it.

This combination is the theoretical basis for our cache's performance. Let's see how it plays out in practice.

2. Time Complexity Analysis of the get Operation

Let's break down the get(key) method from our ThreadSafeLRUCache into its fundamental steps and analyze the complexity of each.

# from previous lesson
def get(self, key) -> int:
    with self.lock:  # Step 1
        if key not in self.cache:  # Step 2
            return -1

        node = self.cache[key]  # Step 3
        self.dll.move_to_head(node)  # Step 4
        return node.value  # Step 5

1. with self.lock:: Acquiring and releasing a lock is a constant-time operation, assuming no contention. For Big O analysis, we analyze the single-threaded case, so this is O(1).
2. key not in self.cache: This is a key lookup in a Python dictionary. The average time complexity is O(1).
3. node = self.cache[key]: This is another key lookup in the dictionary. Again, O(1) on average.
4. self.dll.move_to_head(node): This is the most complex step. Our move_to_head helper method internally performs two actions: remove(node) and prepend(node).
   • remove(node): Because we have a direct reference to node, we don't need to search for it. The operation consists of a fixed number of pointer reassignments (node.prev.next = node.next and node.next.prev = node.prev). This is O(1).
   • prepend(node): This adds the node to the front of the list. It involves updating the pointers of the new node, the dummy head, and the former first node. This is also a fixed number of pointer updates. This is O(1).
   • Therefore, the entire move_to_head operation is O(1) + O(1) = O(1).
5. return node.value: Accessing an attribute of an object is O(1).

Conclusion for get: Every step inside the get method is an O(1) operation. The total time complexity is the sum of these constant-time operations, which remains O(1).

3. Time Complexity Analysis of the put Operation

The put(key, value) method has two main code paths: updating an existing key or inserting a new one. We must analyze both.

# from previous lesson
def put(self, key, value: int) -> None:
    with self.lock:
        if key in self.cache:  # Path 1: Key exists
            node = self.cache[key]
            node.value = value
            self.dll.move_to_head(node)
        else:  # Path 2: New key
            if len(self.cache) >= self.capacity: # Eviction sub-path
                lru_node = self.dll.pop_tail()
                if lru_node:
                    del self.cache[lru_node.key]

            new_node = Node(key, value)
            self.cache[key] = new_node
            self.dll.prepend(new_node)

Path 1: Key Exists

1. if key in self.cache: Dictionary lookup. O(1).
2. node = self.cache[key]: Dictionary lookup. O(1).
3. node.value = value: Attribute assignment. O(1).
4. self.dll.move_to_head(node): As analyzed before, this is O(1).

The total complexity for updating an existing key is O(1).

Path 2: New Key

This path is slightly more complex as it might involve eviction.

1. if len(self.cache) >= self.capacity: Checking the size of a dictionary is O(1).
2. Eviction Sub-path (if capacity is reached):
   • lru_node = self.dll.pop_tail(): This operation finds the node just before the dummy tail (self.tail.prev) and removes it. Finding self.tail.prev is a single pointer access (O(1)), and removing the node is also O(1). Thus, pop_tail is O(1).
   • del self.cache[lru_node.key]: Deleting an item from a dictionary by key is O(1) on average.
3. new_node = Node(key, value): Object instantiation. O(1).
4. self.cache[key] = new_node: Dictionary insertion. O(1) on average.
5. self.dll.prepend(new_node): Adding a node to the head of the list. As analyzed before, this is O(1).

Conclusion for put: Both the update path and the new-key-insertion path (including eviction) consist of a series of O(1) operations. Therefore, the overall time complexity of the put method is O(1).

To solidify this analysis, the following reading breaks down the complexity in a similar, structured manner.

Summary of Key Takeaways

This lesson confirms that our from-scratch LRU cache design meets its critical performance requirement.

• get is O(1) because it uses a hash map for immediate lookup and then performs a constant number of pointer updates to move the accessed node to the front of the list.
• put is O(1) because whether it's updating an existing node or inserting a new one, all underlying operations are constant-time. This includes hash map lookups/insertions and doubly linked list manipulations (adding to head, removing from tail).
• The entire design's efficiency hinges on the synergy between the two data structures: the hash map provides the O(1) access, and the doubly linked list provides the O(1) reordering capability once access is gained.

Next Lesson Preview

We have now designed, implemented, and analyzed our own production-quality LRU cache. But in a real-world scenario, you always face a "build vs. buy" decision. Python's standard library offers collections.OrderedDict, which can also be used to build an LRU cache.

In the next lesson, we will compare our from-scratch LRU cache implementation with one using collections.OrderedDict, focusing on the trade-offs. This will cover aspects like performance, code complexity, and maintainability, aligning perfectly with your preference for dissecting engineering trade-offs.