Search code examples
c#arraystime-complexitybig-ocontains

C# Time complexity of Array[T].Contains(T item) vs HashSet<T>.Contains(T item)

HashSet(T).Contains(T) (inherited from ICollection<T>.Contains(T)) has a time complexity of O(1).
So, I'm wondering what the complexity of a class member array containing integers would be as I strive to achieve O(1) and don't need the existence checks of HashSet(T).Add(T).

Since built-in types are not shown in the .NET reference source, I have no chance of finding found the array implementation of IList(T).Contains(T).

Any (further) reading material or reference would be very much appreciated.

Solution

  • You can see source code of Array with any reflector (maybe online too, didn't check). IList.Contains is just:

    Array.IndexOf(this,value) >= this.GetLowerBound(0);

    And Array.IndexOf calls Array.IndexOf<T>, which, after a bunch of consistency checks, redirects to

    EqualityComparer<T>.Default.IndexOf(array, value, startIndex, count)

    And that one finally does:

    int num = startIndex + count;
for (int index = startIndex; index < num; ++index)
{
  if (this.Equals(array[index], value))
      return index;
}
return -1;

    So just loops over array with average complexity O(N). Of course that was obvious from the beginning, but just to provide some more evidence.