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. AΘ(1), Θ(n)
2. BΘ(n), Θ(1)
3. CΘ(1), Θ(1)
4. DΘ(n), Θ(n)

Pick an option to check yourself, or open the answer below.

Show answer & explanation

Correct answer: A. Θ(1), Θ(n)

Explanation

Insert appends at the end in Θ(1); extract-min must scan all n elements, Θ(n).