🚀 go-pugleaf

In <BrpsJC.5HE@cs.columbia.edu> amir@cs.columbia.edu (Amiran Eliashvili) writes:


>Hi all:

>	I am trying to come up with an efficient way (fewest number of
>iteration ) to find in a list of numbers (not sorted) two numbers
>whose delta (x - y) is the least. So far I could see O(n^2) and
>possibly n*log(n). Are there any kind souls out there that know of a
>better methods that will improve on the above number of iterations?

Interesting problem.  I would guess the best way boils down to sorting
the list and then running  through  it looking for  the number that is
closest to it's successor.  Now this  can be done in  O(n log  n) time
with no real memory overhead by quicksort.  But since they are numbers
we can do it in O(n) time with a radix or distribution sort.  Thus you
are looking at O(n) time.  It seems to me that you will not  do better
than this.

                                       Anthony