Search code examples
c#time-complexitysortedset

Add to SortedSet<T> and its complexity

MSDN states the following SortedSet(T).Add Method :

If Count is less than the capacity of the internal array, this method is an O(1) operation.

Could someone please explain "how so"? I mean when adding new value we need to find a correct place to add a value (comparing it with another values) and internal implementation looks like a "Red-Black tree" with O (log N) insertion complexity.

Solution

  • The comment is simply wrong. Yes, it is a red-black tree, O(log(n)) for inserts. Taking a look with Reflector bears this out, the private AddIfNotPresent() method contains a while() loop to find the insertion point, using normal red-black node traversal.