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:

- Inserting/removing numbers from heaps of size ‘K’. This will take O(logK)
- 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.