Finding largest difference between two elements in array using at most 3/2n comparisons

Question

I am working on given an unsorted array with integer elements,

A={a_1,a_2,...,a_n}

finding largest difference between two elements in array (max|a_i-a_j|)with using at most 3/2n comparisons in the worst case.(Runtime do not matter and we can't use operations such as max or min).

I really doubt if this is possible: to find the maximum difference of two elements, in the worst case, shouldn't we always need about 2n comparisons, as we need to use about n comparisons to find the largest element of the array and another n comparisons to find the smallest element of the array? I don't see where can I cut the operations.

I have also considered divide and conquer. Suppose I divide this array into 2 subarrays with length n/2, but then I encountered the same problem, as finding maximum and minimum in each subarray with take about n comparisons so there will be 2n comparisons in total.

A hint on how to do this will be really appreciated.

What is the nature of those elements? What operations are allowed? — Andrew Vershinin, Feb 16 '21 at 16:23
cppreference proposes an example of implementation of [std::minmax_element](https://en.cppreference.com/w/cpp/algorithm/minmax_element) with a complexity of `3/2 n`. The basic idea is to process 2 elements by 2 elements. — Damien, Feb 16 '21 at 16:36
The trick is to do pair-wise comparison. The lower ones go to the min candidates and the higher ones to the max candidates. Then you repeat this process. E.g. to get the min you compare the candidates pair-wise and drop all higher ones until 1 number is left. If numbers are equal on first step you add it to both candidates and after that you can just drop one of them. — maraca, Feb 16 '21 at 16:41
@maraca yeah this is perfect! I never thought about doing a pairwise comparison to save comparisons. Tysm! — M. Chen, Feb 16 '21 at 17:00

OmG · Answer 1 · 2021-02-16T16:49:30.183

It is straightforward to show that finding the maximum difference is equal to finding the minimum and maximum of the array elements. On the other hand, you can find the minimum and the maximum of an array simultaneously with 3n/2 comparison (the third method in all common programming languages,i.e., C#, C++, Python, C, and Java):

If n is odd then initialize min and max as the first element.

If n is even then initialize min and max as minimum and maximum of the first two elements respectively.

For the rest of the elements, pick them in pairs and compare their maximum and minimum with max and min respectively.

Total number of comparisons: Different for even and odd n, see below:

 If n is odd:    3*(n-1)/2  
 If n is even:   1 Initial comparison for initializing min and max, 
                      and 3(n-2)/2 comparisons for rest of the elements  
                 =  1 + 3*(n-2)/2 = 3n/2 -2

score 3 · Answer 2 · answered Feb 16 '21 at 16:45

cppreference proposes an example of implementation of std::minmax_element with a complexity of 3/2 n. The basic idea is to process 2 elements by 2 elements.

If A[i+1] > A[i]
    A[i+1] is compared with Max
    A[i] is compared with Min
Else
    A[i] is compared with Max
    A[i+1] is compared with Min

2 elements considered, 3 comparisons -> Complexity O(3/2 n)

Note: in n is odd, last element must be considered separately.

Finding largest difference between two elements in array using at most 3/2n comparisons

2 Answers2