patternMinor
Algorithm to find smallest difference in array
Viewed 0 times
smallestarrayalgorithmdifferencefind
Problem
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?
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?
Solution
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.
(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.
Context
StackExchange Computer Science Q#32558, answer score: 7
Revisions (0)
No revisions yet.