educative.io

Educative

Why time complexity is O(N * K) rather than O(N LogK)?

The time complexity of our algorithm is O(N∗K) where ‘N’ is the total number of elements in the input array and ‘K’ is the size of the sliding window. This is due to the fact that we are going through all the ‘N’ numbers and, while doing so, wу are doing two things:

  1. Inserting/removing numbers from heaps of size ‘K’. This will take O(logK)
  2. Removing the element going out of the sliding window. This will take O(K) as we will be searching this element in an array of size ‘K’ (i.e., a heap).

Can anyone explain me please, why time complexity is exactly O(N * K), when removing the element is O(LogK)? I can’t understand the second point, because it seems to be already covered in first.

The first point means that removing the min element from minHeap takes O(logK).
The second point means that removing a random element from the heap. Since heap is not entirely sorted, so in the worst case, we need to iterate over the entire heap to find that random element, which takes O(K). Theoretically, if we somehow have a reference to that element in the heap and we are able to manually increase or decrease its priority, this step can be done in O(logK), but java’s priorityQueue class does not seem to offer this functionality. Implementing our own heap may help, but it’s non-trivial effort.

3 Likes

@Aden answers the question perfectly. But just to add information to this question, I had the same confusion and it is actually caused by PriorityQueue “remove” function. In java, there are two remove functions.

  1. remove() -> This is to remove the head/root, it takes O(logK) time.
  2. remove(Object o) -> This is to remove an arbitrary object. Finding this object takes O(K) time, and removing it takes O(logK) time.

Reference:

  1. Priority Queue remove complexity time