Home Dashboard Directory Help
Search

Incorrect complexity specified for SortedSet.Add by Jon Skeet


Status: 

Closed
 as Fixed Help for as Fixed


4
0
Sign in
to vote
Type: Bug
ID: 533934
Opened: 2/16/2010 4:10:19 AM
Access Restriction: Public
0
Workaround(s)
view
2
User(s) can reproduce this bug

Description

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.
Details
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
Microsoft
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(http://support.microsoft.com)
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).
Sign in to post a workaround.