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 stackoverflow.com/questions/487258/… — Gerriet
– Gerriet, Commented May 28, 2017 at 9: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
– Le Duong Tuan Anh, Commented May 28, 2017 at 9:58
Read the link that I put into my first comment and maybe think about finding a better teacher ... — Gerriet
– Gerriet, Commented May 28, 2017 at 9:59
Also: in this one stackoverflow.com/questions/16764207/… both variants are discussed in more detail. — Gerriet
– Gerriet, Commented May 28, 2017 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
– Le Duong Tuan Anh, Commented May 28, 2017 at 10:14

TsReaper · Accepted Answer · 2017-05-28 10:23:32Z

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, 2017 at 10:23

answered May 28, 2017 at 10:16

TsReaper

8557 silver badges21 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Le Duong Tuan Anh Over a year ago

there is no hint about sequence. And this is what i have to find! Thank you so much!

gsamaras · Accepted Answer · 2017-05-28 10:02:27Z

0

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.

answered May 28, 2017 at 10:02

gsamaras

73.7k50 gold badges210 silver badges330 bronze badges

1 Comment

Le Duong Tuan Anh Over a year ago

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).

Collectives™ on Stack Overflow

Improving finding Min and Max in Array

2 Answers 2

1 Comment

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related