3) Loop over the following until all elements have been removed : Pass one: Compute and store neighbor comparisons (less, equal, greater). While you are doing this, create a list of minima and maxima. Maximum complexity over all loops is O(n), since the first pass requires n comparisons and subsequent passes need only compare the neighbors to the gaps produced from the removed minima and maxima; there will be a total of n gaps produced over all loops.
Pass two: Find the minimum difference between the extreme points and their left neighbors and between they and their right neighbors. Take the minimum of the result this loop and the previous. Maximum complexity over all loops is O(n), since there cannot be more than n minima or maxima (as they come from the set of original points). Pass three: Remove the minima and maxima. Maximum complexity over all loops is O(n), since there cannot be more than n minima or maxima (as they come from the set of original points).
