educative.io

Time complexity for LRU

Courses
,
#1

Hi,
I am a bit confused on the time complexity mentioned for the LRU cache implementation. It says it is O(n).
But doesn’t the data structure illustrated does everything in O(1) time.
e.g deleting, searching etc. on a linked list has O(n) but the implementation has a hash map which points to the doubly linked node address. Hence wouldn’t it take just O(1) ?

Type your question above this line.

Course: https://www.educative.io/collection/10370001/5614097179082752
Lesson: https://www.educative.io/collection/page/10370001/5614097179082752/4899235524247552

#2

Hi @Taichi
It is 0(n) because get (HashSet) will be O(1) in the average case, but O(n) in the worst case, set (HashSet) will be O(1), i.e., constant, and deletion at the head when adding a new element in the linked list will be Constant, i.e., O(1). But search, deleting, and adding to tail in linked list is O(n). So as there are some possibilities of having O(n) time complexity. So, the overall time complexity will be considered O(n).