Question

Consider a SET of int... add, rem, member are the ops... if we implement this as a linked list, what is the time complexity (worst case) of the ADD operation?

a. O(1)
b. O(n)
c. O(log n)
d. O(n²)

Answer 1

The worst-case time complexity for the ADD operation in a linked list implementation of a set is O(1) if no specific order is kept, and O(n) if the list is sorted or checks for duplicates are needed.

Step-by-step explanation:

When implementing a set as a linked list, the time complexity of the add operation, in the worst case, depends on whether you maintain a sorted order or not. If no ordering is required, adding an element to the linked list is simply a matter of creating a new node and inserting it at the head of the list, which can be done in O(1) time. However, if the list must be kept sorted or if duplicates are not allowed and you need to check for the existence of an element before adding, this would require traversing the entire list in the worst case, leading to an O(n) complexity.