This problem is from + for some reasons, I misread longest into shortest.
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(nk)$$$ or $$$O(n\log{n})$$$? Thank you.
