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

user_12771729 0
Viewed 259

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.

max algorithm
2 Answers

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
user_37688710

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.

user_105533410
Related