What is faster way to compute maximum difference in a vector?

Question

Hi

Suppose we have a vector as below which is not in ascending order.

vector<int> vecInput = {1,9,-2,5,20,3,4,11};

Now assume that task is to find out MAXIMUM absolute difference between vector elements. here in case, expected output is 20-(-2) = 22.

It's always not a good way to loop through all elements and compare with remaining elements to come up with output. This requires two for loop.

One way is to sort vector, find size of vector and get difference between last element value with first value.

Another way is to find max_element and min_element. Substract these values to find output.

Which is best option to come up with solution considering performance aspects?

Answer 1

Finding max and min in array is to compare all values with previously stored max and min.. Correct? One need to use two if conditions also in a loop... right?

Answer 2

The second one. Finding max and min are done in linear time and best sorting algorithm is done in logarithmic time.

Answer 3

It's bad thing I guess as we are looping also with two if conditions

Answer 4

Correct...max and min might be linear, but it's done twice one for each.. where as sorting is done once only... still second one is best one?

Answer 5

Any good sites for performance related articles ??

Answer 6

Ketan Lalcheta, I would suggest to take an online course on algorithms. For beginners, I world recommend Algorithms specialization from Stanford at Coursera: https://www.coursera.org/specializations/algorithms
But there are many online courses on this subject, so you can choose.

Answer 7

Ketan Lalcheta of course 2N is better, then logN.

Answer 8

Finding min and max is better in general case. Sorting requires O(n log n) operations. Even in special cases when you can use O(n) sorting algorithm like radix sort, constant in min-max algorithm will be usually less. The only exception is already sorted input array, but this is not your case.