0

Can anyone explain what is the complexity of Dictionary.ContainsValue?

I know that Dictionary.ContainsKey complexity is O(1).

Theodor Zoulias
  • 34,835
  • 7
  • 69
  • 104
Daxak
  • 17
  • 4
  • _Dictionary.ContainsKey complexity is O(1)_ - Make that : _close to O(1)_ [Dictionary](http://msdn.microsoft.com/en-us/library/xfhwa508.aspx) – TaW Jul 24 '21 at 14:48
  • Somewhat related: [Dictionary runs slow when using ContainsValue()](https://stackoverflow.com/questions/16964768/c-sharp-dictionary-runs-slow-when-using-containsvalue), and [Difference between ContainsKey and ContainsValue in Dictionary?](https://stackoverflow.com/questions/49705908/difference-between-containskey-and-containsvalue-in-dictionary) – Theodor Zoulias Jul 24 '21 at 14:58

2 Answers2

2

Short answer : O(N)

Long Answer :

This method performs a linear search; therefore, the average execution time is proportional to Count. That is, this method is an O(n) operation, where n is Count.

Official documentation

Cid
  • 14,968
  • 4
  • 30
  • 45
  • To make this answer stand out an explanation as to why `ContainsValue` must do a linear search would be great to see. – Enigmativity Jul 25 '21 at 01:47
2

O(n).

This method performs a linear search; therefore, the average execution time is proportional to Count. That is, this method is an O(n) operation, where n is Count.

Particularly, in Dictionary structure the key is generated in a hashing mechanism. When calling to ContainsKey function it computes the hash code argument and checks if this computed argument exists in the hash table.

The value of the dictionary is not hashed and when calling to ContainsValue function the algorithm has to iterate over the values stored until it finds the first matched item (if exists).

Note, if you use this function you might need another structure that will work with a better complexity. You might store all values in a HashSet<T>.

Misha Zaslavsky
  • 8,414
  • 11
  • 70
  • 116
  • To make this answer stand out an explanation as to why `ContainsValue` must do a linear search would be great to see. – Enigmativity Jul 25 '21 at 01:47