[Solved] Time Complexity of remove method of Set

Question

Depending on the underlying implementation a remove in a List / Set can be O(1), O(n) or O(log n) (or some other even bigger complexity for esoteric implementations).

ArrayList remove is O(n) on everything but the last element. Removing the last element in an ArrayList is O(1) (decrementing the size counter and setting the element to null).

Now you are asking about an interface (Set) which has at least two implementations (TreeSet, HashSet) which both offer a different time complexity for removal as would be the case for LinkedList in the List case (which e.g. has O(1) removal of the head).

The set interface doesn’t guarantee an upper bound to the removal but any sane set implementation is at worst O(log n) I would suppose 🙂

Accepted Answer

Depending on the underlying implementation a remove in a List / Set can be O(1), O(n) or O(log n) (or some other even bigger complexity for esoteric implementations).

ArrayList remove is O(n) on everything but the last element. Removing the last element in an ArrayList is O(1) (decrementing the size counter and setting the element to null).

Now you are asking about an interface (Set) which has at least two implementations (TreeSet, HashSet) which both offer a different time complexity for removal as would be the case for LinkedList in the List case (which e.g. has O(1) removal of the head).

The set interface doesn’t guarantee an upper bound to the removal but any sane set implementation is at worst O(log n) I would suppose 🙂