Search code examples
c#linqbig-o

The Big O of Distinct() method with a custom IEqualityComparer

Anyone knows the Big O of the algorithm used in the Distinct() method, with a custom IEqualityComparer?

Solution

  • There's an equal question here on SO about "What guarantees are there on the run-time complexity (Big-O) of LINQ methods?"

    See this section in the answer about distinct:

    Distinct, GroupBy Join, and I believe also the set-aggregation methods (Union, Intersect and Except) use hashing, so they should be close to O(N) instead of O(N²).