Consider the three methods below on a Bag collection; that is, a collection in w
ID: 3801704 • 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:
LINKED LIST WITH SOME ORDER
1. Add will take O(N) time, we need to insert in particular order.
2. Remove will take O(N) time because we need to search and then remove
2. Contains will take O(N) time because we need to search through the entire list and we cant use binary search in Linked List
So, D is the Answer