I think that the easiest way to think about the asymptotic complexity of the nub* functions is in terms of the length n of the input list and the number of unique elements m in that list, as I did in a previous posting. My original point in this thread, which I stated badly, is this: Since array access is constant time, one can imagine an implementation nubIx that has O(n) worst-case time on any Ix datatype, regardless of m. This contrasts with the O(mn) complexity of nub and the O(n log m) complexity of nubOrd on values of type Ix. It is true that for any fixed m any nub* is O(n), but IMHO this fact is a bit misleading; we probably want to think about the asymptotic complexity in m as well as n to get a clear picture of what's going on. Bart Massey bart <at> cs.pdx.edu