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 accommodated.
🎥 Video solution / Text Solution of this question is given below:
In an unsorted array implementation of priority queue:
For Insert operation, we can insert the new element directly at the end of the array.
So, worst case time for Insert is:
$\theta(1)$
For Extract-min operation, the array is unsorted, so we must search the entire array to find the minimum element.
So, worst case time for Extract-min is:
$\theta(n)$