dotnet / dotnet/dotnet-api-docs

Complexity analyis seems wrong

Open
#11,605 0 comments 0 reactions 0 assignees View on GitHub
area-System.Collections untriaged
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

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.