To pop an element off of a priority queue, the worst-case complexity is:
O(logN) where N is the number of elements.
Now if you do K pop operations on the priority queue, the number of elements decreases.
So the cost of these K operations would be:
O(logN) + O(log(N-1)) + O(log(N-2)) + O(log(N-3))... O(log(N-K))
How do you add these terms up? if K was a fixed number you could just amortize all of these terms to O(logN) and add them up together, so the sum becomes O(KlogN). But K is not a constant, it depends on the input!
If I wanted to pick top 5 elements from a 1000 elements, K = 5 & N = 1000. If I wanted to pick 10 elements, K would be 10.
How do you derive the cost of performing K pop operations on a priority queue?
Edit: I meant a priority queue implemented that is implemented using a heap