Please solve this question correct ASAP. Choose the best answer from the options
ID: 3801562 • Letter: P
Question
Please solve this question correct ASAP.
Choose the best answer from the options provided. Consider the three methods below on a Set collection; that is, a collection in S 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. acid O(N), remove O(N), contains O(N)Explanation / Answer
Option (D) is correct but Conditions apply
Option(A) could have been a correct answer if the pointers would have given to the location where we want to add an element or remove an element.
These are the worst time complexities Please read the given explanation carefully.
According to the question the set values are stored using a singly linked list in ascending order.So to add some value to the linked list, First, we have to iterate through the linked list to get the knowledge that where this new value will take place in linked list of ascending order set values,In worst case this search can go till end.After getting the pointer to that place where we want to add the new value the add() function takes only O(1) time. In question it is clear that the add() function have only 1 parameter which is new value and not providing the information about the pointer to location where the new value will be added.so it is clear that first we have to iterate through the linked list to get the position of new value.so the time complexity could be O(N) in worst case.
For ex: 1->2->5->9->13->15 Now I want to add 14,so we have to iterate through the linked list
temp = head;
while(temp->next->data < data)
{
temp = temp->next;
}
this is how we get the pointer to that location.
Same time comlexity will be applied to remove the element also.To remove an element first, search for the element in linked list ,In worst case search can go till end of linked llist so time complexity O(N).
For Contain method it is simply a search that linked list contain this element or not .so worst time complexity would be O(N).