Add to SortedSet<T> and its complexity

c# time-complexity sortedset
Andrey Taptunov picture Andrey Taptunov · Mar 28, 2010 · Viewed 11.5k times · Source

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.

Answer

Hans Passant picture Hans Passant · Mar 28, 2010

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.

This doc bug has already been submitted by you-know-who.

Related questions

What is the complexity of these Dictionary methods?

Can anyone explain what is the complexity of the following Dictionary methods? ContainsKey(key) Add(key,value); I'm trying to figure out the complexity of a method I wrote: public void DistinctWords(String s) { Dictionary<string,string> d = …

Read More
If strings are immutable in .NET, then why does Substring take O(n) time?

Given that strings are immutable in .NET, I'm wondering why they have been designed such that string.Substring() takes O(substring.Length) time, instead of O(1)? i.e. what were the tradeoffs, if any?

Read More
How do I generate a random int number?

How do I generate a random integer in C#?

Read More