Consider the three methods below on a Set collection; that is, a collection in w
ID: 3801699 • 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 a singly-linked list for the physical storage of the elements, and suppose that we maintain the nodes in the linked list in ascending order relative to the values they contain. 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? 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 Linked List in ascending Order
Add will take O(N) time, because, we might have to find whether element is already present and so we will traverse the entire list to do it.
Remove will take O(N) time, because, we might have to find whether element is already present and then remove will take O(1) but searching has alreaduy taken O(N)
Contains will take O(N) time, because, Binary Search is not applicable and we might have to traverse whole list to find it.
So D is the Answer