Question

Consider a SET of int... add, rem, member are the ops... if we implement this using an array (not a LIST ADT), 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

Adding an element to a set implemented by an array has a worst-case time complexity of O(n). This is because checking for duplicates or reallocating and copying the array if it's at capacity both require linear time in the size of the array.

Step-by-step explanation:

The question is about the time complexity of the add operation when implementing a set with an array. In the worst case scenario, adding an element to a set implemented by an array can require iterating over the array to ensure no duplicates are added, as a set does not allow duplicate elements. If the array is not sorted and we must check each element for duplicates, the time complexity is O(n), since in the worst case we need to check every element once. If no duplicates are found, appending an element can be done in constant time, but it doesn't change the overall worst-case time complexity.

If the array is at capacity, adding an element may also require allocating a new array and copying all the elements over, which also has a time complexity of O(n). This is because every element from the old array needs to be copied to the new one, and this copying process grows linearly with the number of elements in the array.