2
$\begingroup$

I would like an algorithm that given $n$ numbers, finds the minimum distance between any two unique values.

A trivial way to do this is to sort the numbers in $O(n\log n)$ time, then do a pass in $O(n)$ time through the list, looking at the distance between consecutive terms. This can be done in $O(n\log n)$ time.

However I would like either a faster algorithm, or a proof that there is no faster algorithm (by faster I mean better time complexity).

$\endgroup$
  • 1
    $\begingroup$ Note that such a largest real doesn't exist. You need to change the condition to $m \leq |x - y|$. $\endgroup$ – Yuval Filmus Jul 6 at 13:50
4
$\begingroup$

Suppose that there existed an an algorithm that given a list $S$, finds the minimum of $|x - y|$ over distinct $x,y \in S$. We will show that the algorithm can be used to solve the element distinctness problem with only linear overhead. It is known that element distinctness requires $\Omega(n\log n)$ time in the algebraic decision tree model, so the same lower bound will hold for your problem. This means that if all your algorithm does is compute the sign of linear forms in the input elements (or even of constant degree polynomials), then it needs to do so $\Omega(n\log n)$ times in the worst case.

Suppose we are given a list $x_1,\ldots,x_n$, and we wish to determine whether all of its elements are distinct. Use an algorithm for your problem to compute the minimum distance $m$ between adjacent elements, and compute a new list $y_1,\ldots,y_n$ given by $$ y_i = x_i + \frac{im}{2n}. $$ If $x_i \neq x_j$ then $$ |y_i - y_j| \geq m - \frac{(n-1)m}{2n} > \frac{m}{2}. $$ In contrast, if $x_i = x_j$ then $$ |y_i - y_j| \leq \frac{(n-1)m}{2n} < \frac{m}{2}. $$ Therefore by running an algorithm for your problem on $y_1,\ldots,y_n$, you can determine whether all elements in $x_1,\ldots,x_n$ are distinct.

$\endgroup$

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.