UGC NET Computer Science December 2019 | Question 87

Question 87

---

What is the worst case running time of Insert and Extract-min, in an implementation of a priority queue using an unsorted array? Assume that all insertions can be accomodated.

1. 1. θ(1), θ(n)
2. 2. θ(n), θ(1)
3. 3. θ(1), θ(1)
4. 4. θ(n), θ(n)

Answer : 1. θ(1), θ(n)

Explanation

In the question, given that implementation of priority queue is using an unsorted array

Worst case running time of Insert operation :
Insertion will remain the same for best,average and worst case time complexities. It will take a constant amount of time only.
In the worst case time of insert, we can simply append an element at the end of the unsorted array.
∴ Worst case complexity is θ(1).

Worst case running time of extract min operation :
The Extract-min operation will take θ(n) time for above conditions. The array is unsorted there is naturally no better algorithm than just linear search on the unsorted array. Worst case performance for linear search is θ(n)
∴ Worst case performance will be θ(n)

So, option 1 is correct answer

Reference : Worst-case running time of Insert and Extract-Min

Previous	Next
UGC NET CS December 2019 - Question 86	UGC NET CS December 2019 - Question 88