32. Consider the following two problems.
Nearest Neighbors: Given an unsorted array of n floating-point numbers as input, return two of the
numbers that are closest in value to each other.
Farthest Neighbors: Given an unsorted array of n floating-point numbers as input, return two of the
numbers that are farthest in value from each other.
Assume that the only operations allowed on the data are
• comparing the values of two entries in the array and identifying the larger value;
• comparing the distance between two array entries (the absolute value of the difference between the two
array entries) with the distance between two other array entries;
• swapping two entries in the array.
Further assume that each allowed operation has unit cost. What are the worst-case optimal asymptotic running
times for algorithms that solve the two problems?
Nearest Neighbors Farthest Neighbors
(A) n log n n
(B) n log n n log n
(C) n2 n
(D) n2 n log n
(E) n2 n2
