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.
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this communityWhat 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.
Ben-Or directly proved $\Omega(n\log n)$ lower bounds for several fundamental problems in the algebraic computation tree model:
The first three are the ones most often used in computational geometry.