Algorithms: Design and Analysis, Part 1 - Problem Set 5 - Question 4

Problem:

Suppose you implement the functionality of a priority queue using an unsorted array. What is the worst-case running time of Insert and Extract-Min, respectively? (Assume that you have a large enough array to accommodate the Insertions that you face.)

Solution:

The solution is $ \Theta(1) $ and $ \Theta(n) $

The worst case running time for insertion is easy, one can simply append it in the end of the unsorted array, so $ \Theta(1) $.

The worst case running time for extract min is not so easy to claim because the algorithm is not specified. Apparently since the array is unsorted there is naturally no better algorithm than just linear search. Worst case performance for linear search is $ \Theta(n) $.

The question is, is it possible to have an algorithm that perform better than $ \Theta(n) $? The answer is no and it is proved by the adversary argument. The algorithm can choose what element to read and the adversary is going to give any element that is not minimum until $ n - 1 $ element are read and therefore the adversary forced the algorithm to read through all elements.