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.
EDIT: This answer is wrong, as pointed by nobugz. I'm leaving this answer intact, as some people do find it useful.
First, note that O(1) only means that the complexity is allegedly independant of the input size. That doesn't mean it takes one instruction.
Second, Microsoft sometimes marks methods as O(1) even though they are actually "nearly O(1)". For example, see the Hashtable.Add method: this isn't an O(1) operation, it is just very close to O(1) and quite independant of the collection size. The method hashes the added object, to determine the appropriate "entry point", but since hashing is a many-to-one operation - the method must compare the object with all other objects listed under that hash-entry. Therefore, when adding an object, the actual number of instructions depends on the amount of objects with the same hash value that the collection currently contains. It isn't O(n), because there isn't a direct relation between n and the number of same-hash objects listed, but it isn't O(1) as well. Should microsoft make a comment explaining that this falls somewhere between O(1) and O(n), but isn't O(log n)? that will only confuse the common programmer, trying to make his decisions. In most cases, the operation will act as an O(1) operation, and that is enough for Microsoft to call it O(1).
Thus, I assume the case for SortedSet.Add is much the same - it isn't really O(1), but it may be O(1) for most cases. Probably, SortedSet is somehow based on a collection like HashTable, which has a "near O(1)" add-method complexity.
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.
SortedSet is new collection introduced in C# 4.0.
Below link provides good details about SortedSet
http://www.a2zmenu.com/CSharp/SortedSet-Collection-Class.aspx