Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

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

like image 809
Filip Ekberg Avatar asked Jul 19 '10 07:07

Filip Ekberg


3 Answers

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.

like image 150
Dean Harding Avatar answered Oct 09 '22 21:10

Dean Harding


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).

like image 3
herzmeister Avatar answered Oct 09 '22 21:10

herzmeister


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).

like image 2
Steven Avatar answered Oct 09 '22 23:10

Steven