n here is the number of instances declared for this class. If instance j is more specific than instance i, Hugs inserts j in the tree in front of i and it’s done/no need to search the rest of the tree. If j is apart from every other instance (no overlap), it goes as a leaf of the tree, that needs (j - 1) comparisons to get there. (That’s a fairly crude algorithm, but simple to program.) So it’s only the very last instance that needs (n - 1) comparisons.
It could be made more efficient, if that really becomes an issue. (I guess it might for large classes like Eq.) Organise the tree as a BST-lattice hybrid sorted by the constructor of the first (probably only) type param. OVERLAPPING instances point to their most-specific OVERLAPPABLE. (That’s overkill for Eq, because I don’t think anybody wants overlapping instances in there. Then declare in the class whether overlapping allowed.)