Improving finding Min and Max in Array

Question

my teacher taught me Flash Sort Algorithms, which costs about O(n). Before running that sort, I have to find out which the elements are maximum and minimum in the array.

This is my solution:

//n is a size of array a[]
for(int i = 0; i < n ; i++){
  if (_max < a[i]) _max = a[i];
  if (_min > a[i]) _min = a[i];
}

Let f(n) is a number of conditional operator in that for-loop (excepts comparing variable i). So it costs:

n time for comparing _max with a[i]
n time for comparing _min with a[i]

So, f(n) = 2n.

My friend wrote a code like this:

for(int i = 0; i < n-1; i+=2)
  if (a[i] < a[i+1]){
    if (_max < a[i+1]) _max = a[i+1];
    if (_min > a[i]) _min = a[i];
  }
  else{
    if (_max < a[i]) _max = a[i];
      if (_min > a[i+1]) _min = a[i+1];
  }
// Compare one more time if n is odd
if (n % 2 == 1){
  if (_min > a[n-1]) _min = a[n-1];
  if (_max < a[n-1]) _max = a[n-1];
}

We can easily get f'(n) = 3n/2 + 3. It seems that f'(n) < f(n) when n is large enough.

But my teacher requires that f(n) = n or f(n) = n + a, with a is a const.

Are there any ideas?

Your solution could be sped up a slight bit using an else for the first if-clause. But mainly learn about O-notation, which tells you to ignore constant factors, see https://stackoverflow.com/questions/487258/what-is-a-plain-english-explanation-of-big-o-notation — Gerriet, May 28 '17 at 09:56
@Gerriet can you describe more? My teacher want to count how many operations in for-loop, not only big-O :D — Le Duong Tuan Anh, May 28 '17 at 09:58
Read the link that I put into my first comment and maybe think about finding a better teacher ... — Gerriet, May 28 '17 at 09:59
Also: in this one https://stackoverflow.com/questions/16764207/find-both-min-and-max-together-algorithm-should-be-faster-but-isnt both variants are discussed in more detail. — Gerriet, May 28 '17 at 10:02
hm... I think that the running-time is not important here. My teacher only want to reduce operations in for-loop min-max. In other words, there is any solution using 1 for-loops including 1 if-else to find out min and max values? — Le Duong Tuan Anh, May 28 '17 at 10:14

TsReaper · Accepted Answer · 2017-05-28T10:23:32.463

1

No. It is impossible to find both maximum and minimum value in exactly n(or n+a) comparisons. It will need at least 3n/2 - 2 comparisons. See this proof and this proof. Maybe you can show these proofs to your teacher...

Are there any other hints about the sequence? Like it's uniformly distributed or such?

edited May 28 '17 at 10:23

answered May 28 '17 at 10:16

TsReaper

845
7
19

there is no hint about sequence. And this is what i have to find! Thank you so much! – Le Duong Tuan Anh May 28 '17 at 10:22

score 0 · Answer 2 · answered May 28 '17 at 10:02

When n is large, f'(n) = f(n), because both are of O(n) time complexity.

However, it seems like you need to find min and max once, so your algorithm with time complexity O(n) is OK, since the Flash Sort costs O(n) too, thus the overall time complexity will be dominated by O(n).

In other words:

OverallTime = FindMinMax + FlashSort
OverallTime = O(n) + O(n)
OverallTime = 2*O(n)
OverallTime = O(n)

Even if FindMinMax was faster, the second term of Flash Sort, would still dominate the overall time complexity.

If you must do that faster, you could build a data structure, called Segment Tree, which:

uses O(n log n) storage and can be built in O(n log n) time. Segment trees support searching for all the intervals that contain a query point in O(log n + k), k being the number of retrieved intervals or segments.

In this section my teacher don't care about time complexity in big-O. He require us to improve for-loop to find out min and max elements in array. In other words, I just have to reduce f(n). — Le Duong Tuan Anh, May 28 '17 at 10:12

Improving finding Min and Max in Array

2 Answers2