[Haskell-cafe] Short and sweet

[Neil Mitchell]

Hi

> Can anybody tell me what complexity class "nub" belongs to?

nub requires Eq and not Ord, therefore you can prove that _any_ nub,
no matter how good it is, must be O(n^2).

Thanks

Neil