dotnet
Complexity analyis seems wrong
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
