Incorrect complexity specified for SortedSet.Add - by Jon Skeet

Status : 

  Fixed<br /><br />
		This item has been fixed in the current or upcoming version of this product.<br /><br />
		A more detailed explanation for the resolution of this particular item may have been provided in the comments section.

Sign in
to vote
ID 533934 Comments
Status Closed Workarounds
Type Bug Repros 2
Opened 2/16/2010 4:10:19 AM
Access Restriction Public


The preliminary docs for SortedSet.Add suggest it's an O(1) operation if the Count is less than the capacity of the "internal array".

To start with, I was under the impression that SortedSet is a red/black tree, rather than having an internal array. Furthermore, I believe it's an O(log n) operation rather than O(1). Otherwise one could sort a collection in O(n) complexity by simply adding the values to a SortedSet.
Sign in to post a comment.
Posted by Microsoft on 3/22/2010 at 8:18 PM
Correct. It is O(log n). The documentation will be updated.

Bruce Hamilton
User Education
Developer Division
Posted by Microsoft on 2/16/2010 at 7:02 PM
Thank you for your feedback, we are currently reviewing the issue you have submitted. If this issue is urgent, please contact support directly(
Posted by David A Nelson on 2/16/2010 at 2:36 PM
Reflector seems to confirm that the implementation is a red black tree, which would imply that Add should be O(log n).