This problem is a variation of the following problem:

http://icpcvncentral.tk/public/practice_problem.php?id=I19CE&fbclid=IwAR2j4yF6-LvsAn7ATxinyuo7LYj97MSiDIKCHsclI6dIr-bWgAySbqYRQ98

For some reason, I misread "longest" into "shortest", which made the problem much harder.

My version of this problem:

Given $n$ points $(a_1,0)$, $(a_2,0)$, ..., $(a_n,0)$. Pick $k$ points from $n$ points and calculate the shortest distance $d$ between two points in those $k$ points. Calculate the expected value of $d$.

An easier version of this problem:

$n$ points are $(1,0)$, $(2,0)$, ..., $(n,0)$.

Is this problem solvable in $O(n^3)$, $O(n^2)$, $O(nk)$ or even $O(n\log{n})$? Thank you.