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 MEMBER operation?

a) O(N)
b) O(log N)
c) O(N²)
d) O(1)

Answer 1

The MEMBER operation in a linked list has a worst-case time complexity of O(N) as it may require a full traversal of the list if the sought element is at the end or not present.

Step-by-step explanation:

When searching for an element (the MEMBER operation) in a linked list, you must traverse the list from the beginning until you find the element or reach the end of the list. In the worst case, this requires checking every element in the list. Thus, the time complexity of the MEMBER operation in a linked list is O(N).

Each operation of checking an element is a constant time operation (O(1)), but since you might have to do this for every element in the list (in the worst case), you multiply this constant time operation by the number of elements in the list (N), resulting in O(N) time complexity.

Worst Case Scenario

In the worst case scenario for the MEMBER operation, the element being searched for is either at the end of the linked list or does not exist in the list at all. This situation would require a full traversal of the list, which equates to N operations where N is the number of elements in the list.