Asymptotic complexity of actions on .NET collections

[PeteX]

Hello,

I was wondering if it would be possible to expand the System.Collections documentation so it spells out the big-O cost of the different operations. (Alternatively, it would be enough to state the underlying algorithm, because then the complexity is easy to determine.)

For example, I've just had a need for a sorted list of objects, which must support efficient insertion and deletion. I assume that SortedSet is a red-black tree and will do what I want, but this doesn't seem to be spelt out in the documentation. Another reasonable implementation would be a sorted list, which would support more efficient retrieval (by binary search) but less efficient insertion and deletion.

Thanks for all your work on the documentation and .NET Core itself.

Pete

---

Document details

⚠ Do not edit this section. It is required for docs.microsoft.com ➟ GitHub issue linking.

• ID: 26b9b071-fac4-e286-3dd0-107ed2687a03
• Version Independent ID: 2356f35d-5784-d763-125b-8c5625600a63
• Content: System.Collections.Generic Namespace
• Content Source: xml/ns-System.Collections.Generic.xml
• Service: unspecified
• Product: .net
• GitHub Login: @mairaw
• Microsoft Alias: mairaw

[svick]

Some methods and types have their asymptotic complexity documented, so I think it would help if you listed where exactly do you think complexity is missing.

For example, the documentation for SortedSet<T>.Remove says that it's an O(log n) operation. Though the documentation for SortedSet<T>.Add does not mention complexity, so that's something that should be added.

As for the implementation, it is indeed a red-black tree.

[PeteX]

@svick Yes some of the methods do mention complexity, but as you say not all do, and that's my point really.

Rather than add the asymptotic complexity to all the method descriptions, perhaps a simpler approach would be a summary paragraph in the description of each of the container classes. For example: 'SortedSet is a balanced tree structure which is designed to support O(log n) insertion, retrieval, and deletion.'

[hop-along-polly]

I think this would be ridiculously helpful. I can't tell you the number of times I wish libraries would document this.
I wouldn't mind giving this issue a little bit of my time. Can PR's come in incrementally i.e. one per class or would you prefer one PR with all the changes.

[BillWagner]

@ezzy1337 That would be awesome! One per class would be a great scope. That would help us review and merge in a timely fashion. Ping us if you have any questions as you start making changes.

[hop-along-polly]

Just to be sure this is the .NET framework and not .NET Core right? I didn't see anything specifically spelling out which.

[BillWagner]

@ezzy1337 To be useful, I think it would need to cover .NET Framework and .NET Core. Adding @safern who is responsible for the System.Collections namespace(s).

My thought is the big-O metrics should be similar across implementations, but he would be the authority.

[hop-along-polly]

@BillWagner It looks like the specific documentation is going to live in the dotnet-api-docs repo i.e. for SortedSet.Remove. So after making the change in that repo is there a follow-up PR needed for this repo?