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

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.

Array source code is available in reference source, and can be de-compiled using ILSpy.

In reference source, you find at line 2753 then 2809:

// -----------------------------------------------------------
// ------- Implement ICollection<T> interface methods --------
// -----------------------------------------------------------

...

[SecuritySafeCritical]
bool Contains<T>(T value) {
    //! Warning: "this" is an array, not an SZArrayHelper. See comments above
    //! or you may introduce a security hole!
    T[] _this = JitHelpers.UnsafeCast<T[]>(this);
    return Array.IndexOf(_this, value) != -1;
}

And IndexOf ends up on this IndexOf which is a O(n) algorithm.

internal virtual int IndexOf(T[] array, T value, int startIndex, int count)
{
    int endIndex = startIndex + count;
    for (int i = startIndex; i < endIndex; i++) {
        if (Equals(array[i], value)) return i;
    }
    return -1;
}

Those methods are on a special class SZArrayHelper in same source file, and as explained at line 2721, this is the implementation your are looking for.

// This class is needed to allow an SZ array of type T[] to expose IList<T>,
// IList<T.BaseType>, etc., etc. all the way up to IList<Object>. When the following call is
// made:
//
//   ((IList<T>) (new U[n])).SomeIListMethod()
//
// the interface stub dispatcher treats this as a special case, loads up SZArrayHelper,
// finds the corresponding generic method (matched simply by method name), instantiates
// it for type <T> and executes it.

About achieving O(1) complexity, you should convert it to a HashSet:

var lookupHashSet = new HashSet<T>(yourArray);
...
var hasValue = lookupHashSet.Contains(testValue);

Of course, this conversion is an O(n) operation. If you do not have many lookup to do, it is moot.

Note from documentation on this constructor:

If collection contains duplicates, the set will contain one of each unique element. No exception will be thrown. Therefore, the size of the resulting set is not identical to the size of collection.