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.

  • 9
    $\begingroup$ In what computational model? $\endgroup$ Oct 11 '11 at 5:28
  • $\begingroup$ Good point. I meant the comparision based model. $\endgroup$ Oct 11 '11 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.

  • 3
    $\begingroup$ irrelevant aside: the first three are also the canonical hard problems for communication-complexity-based stream algorithm lower bounds. $\endgroup$ Oct 11 '11 at 14:01
  • $\begingroup$ @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? $\endgroup$ Oct 11 '11 at 19:42
  • 1
    $\begingroup$ 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 $\endgroup$ Oct 11 '11 at 20:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.