Question

Consider a SET of int... add, rem, member are the ops... if we implement this as an array 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 time complexity (worst case) of the ADD operation in an array list implementation of a SET of int is O(n).

Step-by-step explanation:

The time complexity (worst case) of the ADD operation in an array list implementation of a SET of int is O(n). In an array list, when we add an element, we need to check if the array is already full and if so, we need to resize the array and copy all the elements. This resizing operation takes linear time, resulting in an overall time complexity of O(n).