MHB Algorithm with time complexity o(n^2)

[evinda]

Hi! (Smile)

I am looking at the following exercise:

Let $M=\{ y_1, y_2, \dots, y_n \}$ a set of real numbers, where $n \geq 2$. Describe an algorithm, that has time complexity $o(n^2)$ and that finds and returns two elements $y_k$ and $y_l$ of $M$, such that:

$$|y_k-y_l|=\min_{1 \leq i,j \leq n} |y_i-y_j|$$I think that we cannot do this with the use of two while loops, because the time complexity will be $\leq cn^2$, but we want it to be $<cn^2$, or am I wrong? (Thinking)
How else could we do this? (Worried)

 

[johng1]

First sort the values (with say heap sort) of time complexity $n\ln\,n$. Then in the sorted list find the desired elements in one pass of the n elements. Total complexity "little oh" $n^2$.

 

[evinda]

First sort the values (with say heap sort) of time complexity $n\ln\,n$. Then in the sorted list find the desired elements in one pass of the n elements. Total complexity "little oh" $n^2$.

So, is it right like that? (Thinking)

Heapsort(A){
  Buildheap(A);
  for (i=size(A); i>1; --i){
       swap(A[i],A[1]);
       heap_size(A)=heap_size(A)-1;
       Heapify(A,1);
   }
}
 
Elements(S,n){
  int i,min,k;
  Heapsort(S)
  min=abs(S[1]-S[2]);
  for (i=2; i<n; i++){ 
      if (abs(S[i]-S[i+1])<min)
          min=abs(S[i]-S[i+1]);
          k=i;
  }
  return S[k],S[k+1];
}

 

[johng1]

Looks right to me.

 

[evinda]

How could we show the correctness of the algorithm?
Could we prove that it is correct, using induction on [m] i [/m] ?