= Equality-only grouping lower bound
{title2=$\binom n2$}
In the comparison model exposing only an <equality test> between otherwise opaque values, partitioning $n$ values into <equivalence classes> takes $\Omega(n^2)$ tests in the worst case. Run the algorithm on pairwise distinct values. If any pair remains untested, changing just those two values to equal is consistent with every answer observed so far but changes the required output partition. Every pair must therefore be tested. With a compatible <total order>, <comparison sort> can instead group equal values in $O(n\log n)$ time.
Back to article page
