Edit

Share via

Complexity of LINQ OrderBy.First{OrDefault} increased

  • Article

The implementation of OrderBy.First<TSource>(IEnumerable<TSource>, Func<TSource,Boolean>) and OrderBy.FirstOrDefault<TSource>(IEnumerable<TSource>, Func<TSource,Boolean>) has changed, resulting in increased complexity for the operation.

Change description

In .NET Core 1.x - 3.x, calling OrderBy or OrderByDescending followed by First<TSource>(IEnumerable<TSource>, Func<TSource,Boolean>) or FirstOrDefault<TSource>(IEnumerable<TSource>, Func<TSource,Boolean>) operates with O(N) complexity. Since only the first (or default) element is required, only one enumeration is required to find it. However, the predicate that's supplied to First<TSource>(IEnumerable<TSource>, Func<TSource,Boolean>) or FirstOrDefault<TSource>(IEnumerable<TSource>, Func<TSource,Boolean>) is invoked exactly N times, where N is the length of the sequence.

In .NET 5 and later versions, a change was made such that calling OrderBy or OrderByDescending followed by First<TSource>(IEnumerable<TSource>, Func<TSource,Boolean>) or FirstOrDefault<TSource>(IEnumerable<TSource>, Func<TSource,Boolean>) operates with O(N log N) complexity instead of O(N) complexity. However, the predicate that's supplied to First<TSource>(IEnumerable<TSource>, Func<TSource,Boolean>) or FirstOrDefault<TSource>(IEnumerable<TSource>, Func<TSource,Boolean>) may be invoked less than N times, which is more important for overall performance.

Note

This change matches the implementation and complexity of the operation in .NET Framework.

Reason for change

The benefit of invoking the predicate fewer times outweighs a lower overall complexity, so the implementation that was introduced in .NET Core 1.0 was reverted. For more information, see this dotnet/runtime issue.

Version introduced

5.0

No action is required on the developer's part.

Affected APIs