Consider the three methods below on a Set collection; that is, a collection in w
ID: 3801695 • Letter: C
Question
Consider the three methods below on a Set collection; that is, a collection in which no duplicates are allowed and the values are not required to be kept in any particular order. public void add (Comparable value) public void remove (Comparable value) public void contains (Comparable value) Suppose we implement this collection using an array for the physical storage of the elements, and suppose that we maintain the array values in ascending order. Based on the ideas and techniques we have discussed to this point in class, which of the time complexity profiles below characterize the most efficient implementation strategy that you could guarantee? Assume amortization is included as appropriate to account for array resizing in those marked O(1). A. add O(1), remove O(1), contains O(N) B. add O(log N), remove O(log N), contains O(log N) C. add O(N), remove O(N), contains O(log N) D. add O(N), remove O(N), contains O(N)Explanation / Answer
As its mentioned Array in ascending Order
Add will take O(N) time, because, we might have to find whether element is already present and so we might use Binary search for it and then shift to maintain its correct position
Remove will take O(N) time, because, we might have to find whether element is already present and then remove and shift as well so Its O(N)
Contains will take O(Log N) time, because, we will be using Binary Search
So C is the Answer