4. (8) Ordered-array implementation of a set. Suppose you implement the set data

Question

4. (8) Ordered-array implementation of a set. Suppose you implement the set data type using an ordered array. That is, you maintain the N keys in the set in ascending order in an array. What is the order of growth of the Worst-case running time of each of the operations below. Write down the best answer in the space provided using one of the following possibilities. ogN sqrt (N) NlogN N2 function description performance add the key to the set add(key) contains (key) is the key in the set? ceiling (key) smallest key in the set key nume of keys in set smaller than rank (key) given key ith largest key in the set select(i) smallest key in the set min() delete (key) delete the given key from the set Literatoro iterate over all N keys in order

Explanation / Answer

add - N (need to iterate just once since the rest is already sorted)

contains - logN (binary search on a sorted list)

ceiling - N

rank - logN (slight variant of binary search)

select - 1 (since the array is already sorted)

min - 1 (since the array is already sorted)

delete - N (need to iterate once at max)

iterator - N (need to iterate once)

Related Questions

Navigate

• Browse (All)
• Browse 4
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.