dotnet / dotnet/dotnet-api-docs
Complexity analyis seems wrong
- Dominant language
- C#
- Stars
- 949
- Forks
- 1.7k
- Avg merge
- 3d 27m
- Merged PRs (30d)
- 49
Description
### 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(n*log(m)) time when iterating over it self and checking the other, O(m*log(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
Contributor guide
Assessment
This issue has not been assessed yet.