CODEWITHSUNDEEP
algorithmsortingmaxmin
Le Duong Tuan Anh
Le Duong Tuan Anh

Reputation: 360

Improving finding Min and Max in Array

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:

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?

Upvotes: 3

Views: 217

Answers (2)

TsReaper
TsReaper

Reputation: 845

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?

Upvotes: 1

gsamaras
gsamaras

Reputation: 73366

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.

Upvotes: 0

Related Questions