complexity of set::insert
37,992
std::set
is commonly implemented as a red-black binary search tree. Insertion on this data structure has a worst-case of O(log(n)) complexity, as the tree is kept balanced.
Author by
bibbsey
Updated on January 15, 2020Comments
-
bibbsey over 4 years
I have read that insert operation in a set takes only log(n) time. How is that possible?
To insert, first we have find the location in the sorted array where the new element must sit. Using binary search it takes log(n). Then to insert in that location, all the elements succeeding it should be shifted one place to the right. It takes another n time.
My doubt is based on my understanding that set is implemented as an array and elements are stored in sorted order. Please correct me if my understanding is wrong.