- #1

evinda

Gold Member

MHB

- 3,836

- 0

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)