CODEWITHSUNDEEP
c++stlsettime-complexity
bibbsey
bibbsey

Reputation: 1029

complexity of set::insert

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.

Upvotes: 27

Views: 53210

Answers (3)

Nabil Sarwar Rahat
Nabil Sarwar Rahat

Reputation: 1

Intermediry Data Structure Red-Black Tree ||| Inserting 1 Element log(n) time ||| n element nlog(n) time

Upvotes: 0

David Coletta
David Coletta

Reputation: 11

Things do not get shifted over when inserting to a set. It is usually not stored as a vector or array, but rather a binary tree. All you do is add a new leaf node, which takes O(1). So in total insertion takes O(log(n))

Upvotes: 1

cdhowie
cdhowie

Reputation: 168988

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.

Upvotes: 60

Related Questions