4

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

Graviton
  • 79,554
  • 141
  • 413
  • 589
  • In what terms? complexity? time? length? what? – jer Jul 12 '10 at 07:53
  • @jer, Big O doesn't define such things. – Filip Ekberg Jul 12 '10 at 07:54
  • 3
    Basically approaching `O(n*c)`, where `c` is the complexity of what you are doing in a comparer. – Jaroslav Jandek Jul 12 '10 at 08:00
  • It fully depends on what you are comparing, comparing an int will take less time than comparing two chess-board positions... Also you say its a >>custom<< IEqualityComparer that means you are the only one who knows what it does... If you want an estimate, show us the code. – MrFox Jul 12 '10 at 08:02
  • @Filip, I know, but these days, programmers tend to use it all over the place in various contexts, therefore I asked for clarification. – jer Jul 12 '10 at 08:53
  • Possible duplicate of [What guarantees are there on the run-time complexity (Big-O) of LINQ methods?](https://stackoverflow.com/questions/2799427/what-guarantees-are-there-on-the-run-time-complexity-big-o-of-linq-methods) – Liam Apr 18 '18 at 13:01

1 Answers1

7

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²).

Community
  • 1
  • 1
Filip Ekberg
  • 35,726
  • 18
  • 122
  • 180