Complexity set :: insert

Question

I read that the insert operation in the set only takes log (n). How is this possible?

To insert, we first find the location in the sorted array where the new element should sit. Using binary search, log (n) is required. Then, to insert into this place, all subsequent elements should be shifted one place to the right. This takes another n time.

My doubt is based on my understanding that the set is implemented as an array, and the elements are stored in sorted order. Please correct me if my understanding is wrong.

Answer 1

std::set usually implemented as a tree with a red black binary search. Insertion into this data structure has the worst case complexity O (log (n)), since the tree is balanced.

Answer 2

HashSet, LinkedHashSet, and EnumSet have a constant cost of add (), remove () and contain () O (1) time due to the internal implementation of HashMap.

For the tree structure TreeMap and ConcurrentSkipListMap, the time of the put (), get (), remove (), containsKey () operations is O (log (n)).

therefore TreeSet has O (log (n)) time complexity.