edited by
749 views
0 votes
0 votes

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 the insertions can be accomodated.

  1. $\theta(1), \theta(n)$
  2. $\theta(n), \theta(1)$
  3. $\theta(1), \theta(1)$
  4. $\theta(n), \theta(n)$
edited by

3 Answers

1 votes
1 votes

$\underline{\textbf{Answer:}\Rightarrow}\;\;\color{magenta}{\text{option:}(1)}\;\;\Theta(1)\;\text{and}\;\Theta(\mathrm n)$

$\underline{\textbf{Explanation}\Rightarrow}$

$\mathbf{"Unsorted\;Array"}$ is given in the question.

In the $\color{blue}{\text{worst case time of insert}}$, we can simply append an element at the end of the unsorted array.

$\therefore$ Worst case complexity is $\mathbf{\Theta(1)}$.

In the case of $\color{blue}{\text{extract min}}$, there is no specific algorithm for it. So, the only way is to do the linear search on the unsorted array.

$\therefore$ Worst case performance will be $\mathbf{\Theta(n)}$


For $\mathbf{"Sorted \;Array"}$, go through the below link:

https://stackoverflow.com/questions/28807221/questions-about-heaps-in-courseras-open-course

0 votes
0 votes
Insert, extract – min is performed on unsorted array.
Insert: It means insertion of element in unsorted array. In the worst case, element is inserted at the
end of the queue. Simply inserting the element at the end of queue takes O(1) complexity.
Extract –min: To do extract – min, use linear search approach for worst case to find the minimum
element. For this, we need to traverse all the elements of the queue in worst case. So, it will take
O(n) time complexity to extract –min in priority queue.

Related questions

1 votes
1 votes
2 answers
1
4 votes
4 votes
6 answers
3
soujanyareddy13 asked May 12, 2021
1,862 views
The Boolean expression $AB+A \overline{B}+\overline{A}C+AC$ is unaffected by the value of the Boolean variable _________.$A$$B$$C$$A, B$ and $C$