Consider the three methods below on a Bag collection; that is, a collection in w
ID: 3801700 • 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 no specific 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:
1. Add will take O(1) time, just add at the end.
2. Remove will take O(N) time because we need to search and then remove and shift as well
2. Contains will take O(N) time because we need to search through the entire array
So, A is the Answer