What is the worst case running time of Insert and Extract-min, in an…
2019
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 accommodated.
- A.
\(𝜃(1),𝜃(𝑛) \) - B.
\(𝜃(𝑛),𝜃(1) \) - C.
\(𝜃(1),𝜃(1) \) - D.
\( 𝜃(𝑛),𝜃(𝑛)\)
Attempted by 355 students.
Show answer & explanation
Correct answer: A
Final answer: Θ(1), Θ(n)
Reasoning:
Insert: Θ(1) — You can append the new element at the end of the unsorted array in constant time (assuming capacity is available).
Extract-min: Θ(n) — To find the minimum you must examine each of the n elements, which takes linear time. Removing the found element can be done in Θ(1) by swapping it with the last element and popping, but the linear scan dominates, so the overall cost is Θ(n).
A video solution is available for this question — log in and enroll to watch it.