<p>What is the fastest way to find out whether two <code>ICollection&lt;T&gt;</code> collections contain precisely the same entries? Brute force is clear, I was wondering if there is a more elegant method.</p>

<p>We are using C# 2.0, so no extension methods if possible, please!</p>

<p>Edit: the answer would be interesting both for ordered and unordered collections, and would hopefully be different for each.</p>

Brute force takes O(n) - comparing all elements (assuming they are sorted), which I would think is the best you could do - unless there is some property of the data that makes it easier.
I guess for the case of not sorted, its O(n*n).
In which case, I would think a solution based around a
merge sort
would probably help.
For example, could you re-model it so that there was only one collection? Or 3 collections, one for those in collection A only, one for B only and for in both - so if the A only and B only are empty - then they are the same... I am probably going off on totally the wrong tangent here...