Is Enumerable.ElementAt<TSource> O(1) for HashSet?

Question

Is the implementation in HashSet.ElementAt O(1) and if not, what is it?

Answer 1

No, it's O(n). All of the extension methods on IEnumerable<T> are, by necessity O(n) (because the only thing that IEnumerable<T> can do is ... enumerate). Although, as pointed out in the comments, they do attempt to cast to an interface that can implement the operation faster (for example, ElementAt will try to cast to IList<T> in order to implement an O(1) operation). Not that that helps in the case of HashSet<T> which doesn't implement IList<T> anyway.

For HashSet<T> the concept of "ElementAt" doesn't really make sense anyway, because there is no "ordering" as such. You're basically just getting a random element.

Answer 2

It depends on the underyling list type. Reflector shows that Enumerable<T>.ElementAt(...) tries to cast to an IList<T> first. In that case it would be O(1).

A query provider for example might return something that is an IList<T>. But chances are that if you apply any of the Linq operators, it will turn into an IEnumerable<T>, because they are built merely using different enumerators, and it will become O(n).

EDIT: I overread the HashSet. A HashSet<T> doesn't implement IList<T>, thus it is O(n).

Answer 3

There is no ElementAt method in HashSet so you probably want to know the performance of the Enumerable.ElementAt method when used on an instance of HashSet<T>.

The Enumerable.ElementAt method has an optimization for types implementing IList<T>. In that case the performance is O(1). However, HashSet does not implement this interface, therefore, the performance is O(n).