# Problems to reduce from to prove an $\Omega(n\log n)$ lower bound

What are the standard problems we can reduce from to prove $\Omega(n\log n)$ lower bounds?

Of course, state problems other than sorting and element distinctness.

• In what computational model? Oct 11, 2011 at 5:28
• Good point. I meant the comparision based model. Oct 11, 2011 at 19:39

Ben-Or directly proved $\Omega(n\log n)$ lower bounds for several fundamental problems in the algebraic computation tree model:

• Element distinctness: Given an array of $n$ real numbers, are its elements distinct?
• Set disjointness: Given two sets of $n$ real numbers, do they have an element in common?
• Set equality: Given two sets of $n$ real numbers, is one array a permutation of the other?
• Measure problem: Given $n$ real intervals, what is the total length of their union?
• Set inclusion: Given two sets of real numbers, is one a subset of the other?
• Permutation Parity: Given an permutation of the set $[n]$, is the permutation even or odd?

The first three are the ones most often used in computational geometry.

• irrelevant aside: the first three are also the canonical hard problems for communication-complexity-based stream algorithm lower bounds. Oct 11, 2011 at 14:01
• @SureshVenkat - I have seen set disjointness and set equality being used for proving lower bounds in streaming. Do you have an example for element distinctness? Oct 11, 2011 at 19:42
• At least one place I saw it was in the analysis of algorithms under the W-stream model. In general, ED is closely related to bit-vector (or set) disjointness Oct 11, 2011 at 20:14