Complexity analyis seems wrong

[MichaelVerschaeve]

Type of issue

Typo

Description

The complexity analysis seems of to me.
Intersecting two sorted lists with the same comparator can be done in O(nlog(m)) time when iterating over it self and checking the other, O(mlog(n)) when iterating over other and checking self or O(n+m) (iterating over both simultaneously and just keeping the ones matching). It cannot simply be O(n) especially if m dwarfs n.

If the other parameter is a random IEnumerable, it seems to me the best that can be done is O(m*log(n)+n)) by iterating over all in other and marking the ones in self that should be retained, and then copying the retained ones.

Page URL

https://learn.microsoft.com/en-us/dotnet/api/system.collections.generic.sortedset-1.intersectwith?view=net-9.0

Content source URL

https://github.com/dotnet/dotnet-api-docs/blob/main/xml/System.Collections.Generic/SortedSet`1.xml

Document Version Independent Id

150ad48b-f694-f82e-1129-b4cba07e1d8f

Platform Id

9dcd4984-b61b-3d24-09ef-e92d059f0cfe

Article author

@dotnet-bot