# What is the amortized cost of pulling top K elements from a priority queue?

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

• Note that trivially, O(log(N)) + O(log(N-1)) + O(log(N-2)) + O(log(N-3))... O(log(N-K)) ⊆ O(log(N)) + O(log(N)) + ... + O(log(N)) = O(K log(N). It turns out that the other direction is true too, so this is an equality and not just a set inclusion. The intuitive reason is that log is a very slow function which flattens everything. For most values of i, log(N-i) is very close to log(N).
– Stef
May 31, 2022 at 8:16
• Hey I think you are looking for tighter bound than O(nlogn) for removing n elements from priority queue of n elements. It doesn't exist. Try using summation n/2*h + n/4(h-1) + n/8(h-2) + .... where h is height of the tree last level n/2 elements take n/2*h operations then n/4 elements take n/4*(h-1) operation and so on... Sum it you get of the order of O(nh) which is O(nlogn). Dec 5, 2022 at 6:19

• The way your answer is currently phrased, it sounds as if you're only giving an example: "if N-K = sqrt(N), then...". However, you've actually proven that no matter the value of k, the big-O of the sum will not change, because most of the log(N-i) terms in the sum are very close to log(N). It would be worth rephrasing your answer to make it clear it's a general proof and not just an example in the particular case K = N - sqrt(N).