Problem:
Suppose you implement the functionality of a priority queue using a sorted array (e.g., from biggest to smallest). What is the worst-case running time of Insert and Extract-Min, respectively? (Assume that you have a large enough array to accommodate the Insertions that you face.)
Solution:
Θ(n) and Θ(1)
In the worst case, the element being inserted is the biggest one and therefore we have to shift the whole array, therefore Θ(n).
For delete min, we simply take the last one in the array (presumably we maintained a variable for the length of the array) and reduce the variable by 1. All of these work are constant time, so Θ(1)
Suppose you implement the functionality of a priority queue using a sorted array (e.g., from biggest to smallest). What is the worst-case running time of Insert and Extract-Min, respectively? (Assume that you have a large enough array to accommodate the Insertions that you face.)
Solution:
Θ(n) and Θ(1)
In the worst case, the element being inserted is the biggest one and therefore we have to shift the whole array, therefore Θ(n).
For delete min, we simply take the last one in the array (presumably we maintained a variable for the length of the array) and reduce the variable by 1. All of these work are constant time, so Θ(1)
No comments:
Post a Comment