0

When we call the Contains() method on HashSet, the time it takes is O(1). Can anyone let me know how much time will be taken by LINQ Where clause on HashSet? Will it same O(1) or it would iterate through all data?

eg... HashSet hashData = new HashSet(){"a","b","c","d"};

Here, hashData.Contains() will take O(1) time.

What about this:?

hashData.Where(c => c.Equals("a"))

Amarjeet Kumar
  • 93
  • 2
  • 8
  • 6
    It will iterate all the data, so it will be O(N). – Lasse V. Karlsen Jun 22 '20 at 06:23
  • 1
    Does this answer your question? [LINQ Ring: Any() vs Contains() for Huge Collections](https://stackoverflow.com/questions/4445219/linq-ring-any-vs-contains-for-huge-collections) – Abhishek Jun 22 '20 at 06:26
  • 1
    The sames as if you used a foreach – TheGeneral Jun 22 '20 at 06:27
  • 1
    As stated above, `hashData.Where(c => c.Equals("a"))` is O(N) but be aware that it will only be executed if you actually use `foreach` or some other looping construct to loop over the elements of the returned sequence. The call `hashData.Where(c => c.Equals("a"))` on its own is O(1). – Matthew Watson Jun 22 '20 at 07:58
  • Hash is binary tree so performance is Log2(N). – jdweng Jun 22 '20 at 08:19

0 Answers0