8
$\begingroup$

We want an algorithm that, given an array of length $n$ of integers, find the minimum difference between two integers in the array.

One such algorithm is to sort the array and check adjacent pairs of numbers. This takes time $O(n\log n)$.

Is there a faster way, e.g., an $O(n)$ algorithm?

$\endgroup$
  • $\begingroup$ $O(n)$ is not faster than $O(n\log n)$ $\endgroup$ – David Merinos Nov 8 '14 at 22:12
7
$\begingroup$

This depends on your model of computation. If you only allow arithmetic and comparisons (the algebraic decision tree model) then there is an $\Omega(n\log n)$ lower bound for element distinctness, the problem of deciding whether all elements are distinct. Your problem is of course even harder, so the same lower bound applies.

(There is some fine print: the lower bound only holds if the degree of the polynomials being compared is bounded. If all you're doing is comparing various differences $x_i - x_j$, then you're good to go. The algebraic decision tree model also allows you to compare more general polynomials in the inputs, as long as they have bounded degree.)

There are other models which might perform better — for example, in some models you can sort integers in $o(n\log n)$. But I imagine you don't want to allow the sort of trickery used in such algorithms.

$\endgroup$
  • $\begingroup$ Thanks. What do you mean by "comparing various differences $x_i-x_j$"? Since there are $\Theta(n^2)$ such pairs, wouldn't that take time $\Omega(n^2)$? $\endgroup$ – boaten Nov 1 '14 at 18:34
  • $\begingroup$ Not necessarily. Comparison-based algorithms are only allowed to compare pairs of elements. Here I'm allowing you to make more complicated queries such as $x_1 - x_2 > x_3 - x_4$, or even $x_1 + 5x_8 - 17x_3 < -5$. We know that there is a solution that uses $O(n\log n)$ comparisons of the type $x_i > x_j$, and $O(n)$ comparisons of the type $x_i - x_j > x_k - x_\ell$. The question is, can you do better, and the answer is no, if you're only restricted to making linear queries (or, more generally, bounded degree queries). $\endgroup$ – Yuval Filmus Nov 1 '14 at 18:47
  • $\begingroup$ Not sure I understand the practical significance of this bound for element distinctness. Wouldn't you have an expected O(n) with a hash table? $\endgroup$ – jkff Nov 3 '14 at 2:04
  • $\begingroup$ A hash table cannot be implemented using this model of computation. In general, lower bounds are hard to prove. The algebraic decision tree model is one in which non-trivial lower bounds are provable. I don't see how to prove an $\omega(n)$ lower bound in any other model – indeed, such lower bounds are typically known only for random functions. You're right that there might be a trick $o(n\log n)$ algorithm which goes beyond this model, but I can't think of any. $\endgroup$ – Yuval Filmus Nov 3 '14 at 3:33
-1
$\begingroup$

If integers in the array has a limited number of digits you can sort an array with radix sort algorithm, that is O(kN) and than check the adjacent pairs of numbers (O(N))? Resulting complexity will be O((k+1)N), linear.

$\endgroup$
  • 1
    $\begingroup$ Be mindful of the conditions under which the runtime of radix sort is actually good. $\endgroup$ – Raphael Nov 7 '14 at 15:13
  • $\begingroup$ @Raphael Well, original question was does the linear algorithm exist, so I thought about it. You mean that k will be larger than log(N) for small N? $\endgroup$ – Pavel Davydov Nov 7 '14 at 16:38
  • $\begingroup$ $k$ and $N$ are independent parameters, which is why radix sort is not a linear-time algorithm for all inputs, and hence does no contradict the $\Omega(n \log n)$ bound on (comparison) sorting. (The Wikipedia article explains this, too.) $\endgroup$ – Raphael Nov 7 '14 at 17:05
  • $\begingroup$ @Raphael Yes, but for array of integers that are less the 64 bits (that is quite common case) it will be linear. I'll edit my answer. Thanks for your comments. $\endgroup$ – Pavel Davydov Nov 7 '14 at 17:59

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.