the element-distinctness lower bound

Element distinctness asks a simple yes/no question: given n numbers, are they all different, or is some value repeated? You could solve it by sorting (n log n) and then scanning neighbours, or by hashing (expected linear). The element-distinctness lower bound proves that, in a natural model where you manipulate the numbers by arithmetic and comparisons, you cannot reliably beat Omega(n log n) — a clean linear-time answer is impossible there. This single problem is a workhorse for proving other geometric and sorting-related tasks are hard.

The bound lives in the algebraic decision-tree model, where each step computes a polynomial of the inputs and branches on its sign (positive, zero, negative), generalising plain comparisons. The proof idea, due to Ben-Or, is geometric. Think of an input as a point in n-dimensional space. The 'all distinct' inputs form a region, and that region is shattered into a huge number of disconnected pieces — roughly n! of them, one for each ordering of the n values, because to move from one ordering to another you must pass through a point where two coordinates are equal (a 'not distinct' input). A decision tree of height h can carve space into at most a bounded number of pieces, growing like a constant raised to the h. To separate n! connected pieces you therefore need height h = Omega(log(n!)) = Omega(n log n). The geometry of disconnected components is what forces the depth.

Honest scope. The bound is for the algebraic decision-tree model and is a worst-case statement; it does NOT apply to models that escape it. Hashing solves element distinctness in expected O(n), because hashing uses the integer values to index a table rather than only signs of polynomials — so it is not a counterexample, it is outside the model. The reason this bound matters so much is leverage: many problems reduce to or from element distinctness — closest pair, finding whether any three points are collinear, certain set problems — so its Omega(n log n) floor transfers to them by reduction, making it one of the most reused lower bounds in computational geometry.