educative.io

Educative

PriorityExpiryCache: incorrect time complexity of deleting arbitrary node from priority min-heap

In Priority Expiry Cache problem: Priority Expiry Cache Problem - Big-O Notation For Coding Interviews and Beyond

In the solution, for evictItem() expired case, when removing the item from priority min-heap, you say this takes O(logn) time complexity.

However since you need to first find the item in the heap (since it’s may not be min at priority min-heap) that should take O(n) time complexity.

Could you elaborate on why you said O(logn) when removing the expired item from priority min-heap?

Hi @musti
Thanks for reaching out to us. The time complexity to find the minimum element in a priority min-heap is O(1), which is the primary purpose of such a container. It was literally made to find the smallest (or largest) element in constant time. It must not be O(n). Pop/remove operation takes O(logn) because it will remove the smallest (or largest) element, and then force a re-ordering to ensure that the new smallest (or largest) element is now at the top of the heap.
Hope it will help, Happy Learning :slight_smile:

1 Like

No I was not writing about that. I know min-heap is built for that, obviously. The problem is when you need to maintain the heaps on evictItem(), yes for expiry you are deleting the min so O(logn) for that, alright. However you also need to maintain priority min-heap and there your expired record is not necessarily having min-priority. So you need to find the item in priority heap first and then remove. That makes it O(n).

I hope that sounds clear. So what do you think?


Course: Big-O Notation For Coding Interviews and Beyond - Learn Interactively
Lesson: Priority Expiry Cache Problem - Big-O Notation For Coding Interviews and Beyond

Did you understand my point?
When you are removing an expired item:

  • removing the item from expiry min-heap is O(log n) since you’re removing from top
  • removing the item from priority min-heap (since it’s also there) is O(n) since you have to find it first.

That makes the whole approach O(n)

This sentence would be invalid in the text: “We’ll also remove it from the preference min-heap which is another O(lgn) operation.”

Hi @musti
Thanks for pointing this out, we’ll verify it.