Proving priority queue operations time complexity

0
votes

I recently took an exam that had question saying: Your friend has come up with a set of algorithms for a priority queue that do the following operations: Insert(S, x) in O(1), Peek-Max(S) in O(1), Remove-Max(S) in O(1), and Increase-Key(S, x, k) in O(logn). How would you prove to your friend that this set of algorithms is impossible?

I've been really stressed because I'm positive I got the wrong answer. I said a priority queue must have the property that for a set of elements [A1, A2, ... An] it needs to have the relation [A1 >= A2 >=...>= An] which I now realize isn't true. Only the first element needs to be bigger than the rest (assuming a max-first priority queue). Therefore the insert function can't be in O(1) because for a set of n elements there's no way you can make sure the placed item is in its proper spot in constant time.

Do any of you have any insights as to how one would go about solving this problem? I couldn't get any sleep last night thinking I probably got this question wrong.

1
algorithmtime-complexitypriority-queue
Can we insert an element with a predetermined priority value, or do we have to use Increase-Key to increase the priority of an element that already exists in the queue? What exactly does Increase-Key do? – kevchoi

1 Answers

1
votes

An easy way to disprove something is to think of a counter example. In this case, you want to find a sequence of operations that is clearly impossible.

For example, let's say you insert n elements into the queue, and then remove-max n elements. Since this is a priority queue, the elements that we extract should be in sorted order. Thus, with your friend's algorithm, we were able to sort n elements with time complexity O(n). We know that sorting at best is O(nlogn) - sorting in O(n) is impossible!