2
$\begingroup$

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

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ 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). $\endgroup$
    – Stef
    Commented May 31, 2022 at 8:16
  • $\begingroup$ 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). $\endgroup$
    – router
    Commented Dec 5, 2022 at 6:19

1 Answer 1

Reset to default
5
$\begingroup$

Big-O doesn't care about a factor 0.5, for example. Now log sqrt(N) = 1/2 log N. So if you take away enough elements to change the size of the queue from N to sqrt(N), you have multiplied the time by 0.5, which doesn't affect O(N). And there are now only sqrt(N) elements remaining, removing them even if you could do it at zero cost won't change the time complexity either.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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). $\endgroup$
    – Stef
    Commented May 31, 2022 at 8:18
  • $\begingroup$ What if K = N? Surely the O(KlogN) bound will still hold, but I am assuming there would be a tighter bound than O(KlogN)? $\endgroup$
    – Aditya
    Commented Jun 1, 2022 at 0:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.