dotnet / dotnet/dotnet-api-docs

List.InsertRange O() is sometimes wrong

Open
#5,267 0 comments 0 reactions 0 assignees View on GitHub
area-System.Collections Pri3 untriaged
Dominant language
C#
Stars
949
Forks
1.7k
Avg merge
3d 27m
Merged PRs (30d)
49

Description

I was interested in the computational work (only know the German term: Aufwand – is it "effort"?) for the generic List's `InsertRange` method. It looked suspicious because it accepts an `IEnumerable` whose count may not be known in advance. In my specific case, I can use `ToList` to provide that count. But I'll only do so if it helps.

The [documentation](https://docs.microsoft.com/en-us/dotnet/api/system.collections.generic.list-1.insertrange?f1url=%3FappId%3DDev16IDEF1%26l%3DEN-US%26k%3Dk(System.Collections.Generic.List%601.InsertRange);k(DevLang-csharp)%26rd%3Dtrue&view=net-5.0) says it's O(n*m) which would be sad.

The [source](https://source.dot.net/#System.Private.CoreLib/List.cs,79de3e39e69a4811) says there's an optimisation for `ICollection` and it looks more like O(n) instead.

There's no feedback form on that page and editing it wasn't possible through GitHub (they said they created a fork but somehow I couldn't write anything, and the word "InsertRange" wasn't even in that file). So I can only point you to the issue, not provide a solution to it.

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.