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:
$ \Theta(n) $ and $ \Theta(1) $
In the worst case, the element being inserted is the biggest one and therefore we have to shift the whole array, therefore $ \Theta(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 $ \Theta(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:
$ \Theta(n) $ and $ \Theta(1) $
In the worst case, the element being inserted is the biggest one and therefore we have to shift the whole array, therefore $ \Theta(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 $ \Theta(1) $
No comments:
Post a Comment