= Element distinctness problem
Decide whether all input elements are distinct. In the <comparison model>, this needs $\Omega(n\log n)$ comparisons in the worst case. An accepting decision-tree leaf for distinct keys must force a total order: incomparable keys could otherwise be made equal consistently with its strict comparison outcomes. Thus the $n!$ possible orders require different accepting leaves, giving a decision-tree depth of at least $\log_3(n!)=\Omega(n\log n)$ even for three-way comparisons.
Back to article page
