2
$\begingroup$

Given an integer N and an array of N real numbers (which you can compare and add/multiply/divide in O(1)), output 1 if there are two equal numbers and 0 else. This can easily be solved in O(N*log N) worst case time complexity, by sorting and then checking any two adjacent entries if they are equal. The question is: is there an algorithm that does this in o(N*log N) worst case time complexity? (notice the small omicron notation). I've been able to prove that there is no comparison-based algorithm that does this in o(N*log N) (by comparison-based I mean that you are not given the array, but only an orcale that takes as an input two given integers in the array and tells you in O(1) which of the two is bigger (or if they are equal). I can't seem to solve it in less, though. Does anyone know?

2 Answers 2

3

Moving my comment to an answer:

It is known that checking element distinctness requires $\Omega(n \log n)$ comparisons in the algebraic decision tree model.

Rough sketch: You can divide the topological space $A \subset {\mathbb R}^n$ of points with distinct coordinates into $n!$ connected components. After the algorithm has finished it has to know what is the connected component. Otherwise, it could not distinguish being in some component of $A$, and being outside $A$.

For details, see http://en.wikipedia.org/wiki/Element_distinctness_problem and lecture 6 at "Lower bounds in computer science" http://cs.dartmouth.edu/~ac/Teach/CS85-Spring08/lecnotes.pdf

2

Finding duplicates in a list is a standard application of hash tables. But any algorithm must be $\Omega(NM)$ in the worst case, because it takes that long simply to read the array of numbers. You're greatly skewing the analysis by accounting for $M$ in some cases, but neglecting it in a comparison-based algorithm.

  • 0
    But you still need some amount of random access -- to merge two regions, you have to be able to read from both regions. If you have to seek back and forth each time, you can't do a merge operation in `O(N)` time.2012-04-20