Equality test ($a=x$)

A terminating check returning whether two values match under a specified relation. Mathematical equality is one such relation; a chosen equivalence relation can instead express matching keys. Linear search only needs this check, whereas binary search also uses relative order. The cost of an equality test depends on the representation and implementation of its operands.

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.