Consider the three methods below on a Bag collection; that is, a collection in w
ID: 3801701 • Letter: C
Question
Consider the three methods below on a Bag collection; that is, a collection in which 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(N), 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
Bag as we know its an unordered collection that might have duplicates and we dont have to worry on the order:
Now we have to maintain Some order
1. Add will take O(N) time, because we need to find appropriate place and then shift the array elements by 1
2. Remove will take O(N) time because we need to search and then remove and shift as well
2. Contains will take O(log N) time because we need to search through the array and we can use binary search for it
So, C is the Answer