3.4k views

An array of $n$ numbers is given, where $n$ is an even number. The maximum as well as the minimum of these $n$ numbers needs to be determined. Which of the following is TRUE about the number of comparisons needed?

1. At least $2n-c$ comparisons, for some constant $c$ are needed.

2. At most $1.5n-2$ comparisons are needed.

3. At least $n\log_2 n$ comparisons are needed

4. None of the above

asked | 3.4k views
0
how to analyze this que? how it comes 1.5n-2 comparisions.. please explain
0
there 2 appoach to this question tournament approach and divide and conquer....
+1

Although very good answer is already provided. Just mentioning another approach which takes on an avg.  (3/2)*n - 1 or (1/2)(3*n-2) comparison.

Sample code PFA.

import java.util.Scanner;

public class Test {
public static void main(String args[]) {
Scanner in = new Scanner(System.in);
int n = in.nextInt(), a  = in.nextInt(), min  = a, max =a;
for(int i=1; i<n; i++){
a = in.nextInt();
if(a<min) min =a;
else if(a>max) max = a;
}
in.close();
}
}

Best case when array is sorted in decreasing order. (n-1) comparison.

Worst case when array is sorted in increasing order. 2*(n-1) comparison.

So Avg case  = 1/2(Best Case)+1/2(Worst Case) = (3/2)*n - 1

0
can u show me some cases where avg case is calculated like that ??

An easier way to find it is by using Tournament Method Technique -

1. To find the smallest element in the array will take $\mathbf{n-1}$ comparisions.
2. To find the largest element -
a. After the first round of Tournament , there will be exactly  $\mathbf{n/2}$ numbers that will loose the round.
b. So the biggest looser (the largest number) should be among these $50$ loosers.To find the largest number will take  $\mathbf{n/2 - 1}$.

Total Comparisons  $\mathbf{= (n-1) + (n/2 - 1) = 1.5n - 2}$.

answered by Active (3.9k points)
edited by
+3

Nice answer. Why this answer is under rated? +10 votes from me. I feel it should be the best answer.

Those who want to know more about ths technique.  https://gateoverflow.in/20617/tifr2011-b-31

For odd:  n-1 + ( (n-1)/2 +1 ) -1 = 1.5n -1.5

+1

@Ahwan

how n-1 + ( (n-1)/2 +1 ) -1  ?

+6

@srestha
(Before applying this technique, Just click on that TIFR question and read about the theory in that question)

For even:
Min:   n-1 comparisions
Max:   All those who lost in 1st round, they are all leaf nodes in tree...  n/2 such persons are there.
So to find maximum from them....we need  (n/2) - 1 comparisons.
Total:   n-1 + (n/2)-1 = 1.5n -2

For Odd:
Min:   n-1 comparisions
Max:   All those who lost in 1st round, they are all leaf nodes in tree... But remember... odd number of people are there. So lets take out one guy......so we have n-1 guys. (n-1) is even here. We have (n-1)/2 loosers + one guy who was not compared with any one....you can now compare all of them..
So to find maximum from them....we need  {(n-1)/2 + 1} - 1 comparisons  = (n-1)/2
Total:   n-1 + (n-1)/2 = 1.5n - 1.5

0
thanks good @Ahwan :)
0

[need @arjun sir to verify it  ]

We are requested to find the MAX and MIN of the array of $n$ elements . This can be done as follws

Non Divide And Conquer

Max_Min(A,n,max,min)
max=min=a[i]
for i-> 2 to n
{
if A[i] > max   // First Comparision
max=A[i]
else if A[i] < min  // Seond Comparision
min = A[i]
}

Analysis

Best Case

When input is in increasing order

• First Comparision : $n-1$ time
• Second Comparision: $1$ time

Worst Case

When input is in Decreasing order

• First Comparision : $n-1$ time
• Second Comparision: $n-1$ time

Average Case

When First Comparision fails for half of the input

• First Comparision : $n-1$ time
• Second Comparision: $\frac{n}{2}$ time

Divide And Conquer

Given a function to compute on $n$ inputs the divide-and-conquer strategy suggest splitting the inputs into $k$ distinct subsets, $1 < K \leq n$, yielding $k$ sub problems. These Sub problems must be solved, and then a method must be found to combine sub solutions into a solution of the whole.

Defining the Termination condition 'SMALL' of the problem , When $n \leq 2$. In this case, the maximum and minimum are $a[i] \ \text{if} \ n = 1$ . If $n = 2$, the problem can be solved by making one comparison.

How can we Combine The Subproblem ? If $\text{MAX(A)}$ and $\text{MIN(P)}$ are the maximum and minimum of the elements of A, then $\text{MAX(A)}$ is the larger of $\text{MAX(A1)}$ and $\text{MAX(A2)}$ Similarly for $\text{MIN(A)}$

 MaxMin(i, j, max, min)
// a[1:n] is a global array. Parameters i and j are integers,
// 1≤i≤j≤n. The effect is to set max and min to the largest and
// smallest values in a[i:j].
{
if (i=j) then max := min := a[i]; //Small(P)
else if (i=j-1) then // Another case of Small(P)
{
if (a[i] < a[j]) then max := a[j]; min := a[i];
else max := a[i]; min := a[j];
}
else
{
// if P is not small, divide P into sub-problems.
// Find where to split the set.
mid := ( i + j )/2;
// Solve the sub-problems.
MaxMin( i, mid, max, min );
MaxMin( mid+1, j, max1, min1 );
// Combine the solutions.
if (max < max1) then max := max1;
if (min > min1) then min := min1;
}
}

Analysis

Time Complexity

$T(n) =\begin{Bmatrix} 0 & n=1\\ 1 & n=2\\ 2T(\frac{n}{2})+2& n>2 \end{Bmatrix}$

Using Master Theorem  Case 1 follows . Hence $T(n)$ is $\Theta(n)$

Solution

\begin{align*} \\ T(n)&=2T(\frac{n}{2})+2\\ &=4T(\frac{n}{4})+2^{2}+2 \\ & ... \\ & = 2^{k}T(\frac{n}{2^{k}})+\sum_{i=1}^{k}2^{i} & (\text{where}\sum_{i=1}^{k}2^{i}=2^{k+1}-2)\\ &=2^{k}T(\frac{n}{2^{k}})+2^{k+1}-2 & ( \text{where,} \ k=(\log n) -1) \\ &=2^{(\log n) -1}T(1)+2^{\log n} -2 \\ &=\frac{n}{2}+n-2 \\ &=\frac{3n}{2}-2 \end{align*}

For Input Class : Numbers in Increasing Order Non-Divide And Conquer Strategy Perform Better than Divide And Conquer

Space Complexity

$S(n) = n+ \log n + c$ Where $n$ is the input size and $\log n$ is the size of the stack . Hence the space complexity is $O(\log n)$

Example

Consider the array

$A[] = \begin{Bmatrix} 1 &2 &3 &4 & 5 &6 &7 &8 &9 \\ 22 & 13 & -5 &-8 &15 &60 &17 &31 &47 \end{Bmatrix}$

Video Example : https://www.youtube.com/watch?v=EHRL2LbS5LU

References

answered by Boss (22k points)
0
Here n is even that why we require 3(n/2) - 2 comparisions. If n is odd then we require 3(n/2) comparision.
+1
+1
I think more accurate answer is $\lceil \frac{3*n}{2} \rceil -2$.
+2

Best Case

When input is in increasing order

• First Comparision : n−1 time
• Second Comparision: 1 time

Why is second comparision even one time?? If the array is in increasing order it should be zero??

0
For 6 elements, I am getting 8 comparisons but according to formula it's only 7 comparisons . I don't know where am I going wrong.
0
wat is max1 min1 doing in ur code ?? space complexity is O(n) ....
0
This answer was perfect and you changed the best answer :O @Puja Mishra
0
Nope copy pasting is nt perfect ... one should hav their own views ...
0
@Puja_mishra , Space Complexity $O(n)$ How ?

We will not consider the input size while calculating   space complexity . Hence it is $O(\log n )$ only .
max1 is just to keep track of max element in each iteration .
0

See ur code..In ur code max1 does nt look like it is keeping track of anything  ... See

if (max < max1) then max := max1;
if (min > min1) then min := min1;

no value is initialized to max1 or min1 ... and tell me O($n^{2}$+n ) is O($n^{2}$) right ?? in the same O(n+logn+c) should be O(n) ... Try to Give ur own views ... all blogs r not correct ...

0
Space complexity is defined as the sum of the auxiliary space $+$ space required for the input. It would be $O(log(n))$ if it's the auxiliary space mentioned.
0
hello pc

for your without DAC approach

best case : # of second comparison=0

and in avg case # of second comparison= (n-1)/2
0
hello puja

i think , if he use separate variables to keep local max and min by recursive calls and then update the global variable max and min then it will make sense.

like

maxmin(i,mid,max1,min1);

maxmin(mid+1,j,max2,min2);

if (max1<max2) max=max2;

else max=max1;

if (min1<min2) min=min1;

else min=min2;
+2
@Puja_mishra ,

$O(n+ \log n+c) = O(n)$ Only.  I havn't denied but ,  What is n ? It is the input size array and will not be considered for calculating space complexity unless mentioned in question.   Hence the space compleity is $O(\log n)$

My intension was to solve this question using Master Theorem which is a very straight forward approach and thanks for pointing out flaws in code which i didn't notice when I copied the code from blog , will correct it when i get some time , Moreover I have tried to give my views to every questions that  I have answered in GO :)
+2
your time and effort are precious pc.
0
Yeah i hav found where i hav done wrong ... Next time try to give answer with perfection ...Becoz keep in mind there is someone like me or anyone is watching the answers and building her or his concept ...I can also refer some random website as an answer every question i hav voted ... Bt i dont do it... instead of that i upvote the correct answer if i dont hav my own view or add reference in the comment of that answer ... simple as that ... This website is good ... bt maximum of the question has redundant answers which are not needed at all ... I mean u hav also seen this kind of question in this site where answer is selected ... bt still some random people is answering D is option without any explanation ...  this is something i found irritating ...
+4
@Puja you do not have to be irritated- you can just ignore and see what you need to see. I saw that this answer is taken from the given reference link -- can you post the same here as done in this answer? It was not a simple copy paste -- it was done with careful formatting and proper reference.
0
ok (y)
divide and conquer gives 1.5n - 2 comparison
answered by Veteran (54.8k points)
–1
didn't get it
0
0
what if two binary searches for min and max, total comparisons = 2logn

... My bad. The array isn't sorted, hence divide and conquer is the best approach.
Using divider and conquer approach T(n)=2T(n/2) + 2 It comes out to be O(n) but on better analysis it is 1.5n-2 comparisons
answered by Boss (14.1k points)
0
i understand the reccurence relation u give but how u derived / solved it to 1.5- 2? please explain.....

Option B. 3/2n - 2 comparsion Needed.

https://youtu.be/lEvzwEcjQ54?t=1823

answered by Active (4.6k points)
0
worth every sec of time

There are N number: n1, n2, n3, n4, ...... N.

We need to find the minimum and maximum element.

Naive approach: Assign the first number with min and max, and compare every other element linearly with these min and max variable, if we found another number is minimum/maximum, we will update our min and max variable according. Every number is compared twice. Total comparison = 2(n-1) = 2n - 2.

For every number, we are doing 2 comparisons, for every two numbers, we are doing 4 comparisons, Can we reduce this?

Better Algo: Pair all the elements.

(n1, n2) , (n3, n4), (n5, n6) ..........

When N is even, for the first pair, (n1, n2) compare them with each other and find min and max. Now, from every other pair, we first compare them, and whoever is minimum among them we compare it with min, and whoever is maximum among them will be compared with max. So for every other two elements, we have three comparisons.

Total comparison = (3* (n - 2) / 2 ) + 1 (for the first pair).

= (3*n / 2 ) - 3 + 1 = 1.5*n - 2.

When N is odd, Assign the first number with min and max, and now compare them with every other pair as mentioned above.

Total comparison = 3 * (n - 1) / 2

Reference : Cormen

answered by Boss (14.7k points)
edited

i don't want to congest GATE question with much answers! but this qs need litlle derivation

answered by Boss (18.5k points)
edited
0
someone rotate this please

Consider n=8 elements in an array {1,4,5,8,3,2,7,9}
Lets make a tournament bracket for them, where at each stage the winner is the minimum element between the two.

As you can see, number of comparisons being done = n-1 = 7

Similarly, to find the maximum element you again will need n-1 comparisons!
So total no of comparisons to find min and max=2(n-1)
Hmm...there is one optimisation to it !!

The last level in the tree is making n/2 comparisons(4 in this case) and these are being repeated while finding the minimum and maximum! So doing the last level comparisons only once, we do n/2 comparisons less
Hence 2(n-1) - n/2 = 2n-2-n/2 = 3n/2-2

answered by Junior (633 points)