 # Minimum Comparisons Second Largest Element

#1

You have given an array of 64 elements, minimum number of comparisons required to find out second largest element among all will be _______

#2

You can go to these links and get an idea:

#3

max_element = a
second_max_element = some high negative value.

so the logic will be like:

for(i = 1;i<=10;++i)
{
if(a[i] > max_element)
{
second_max_element = max_element ;
max_element = a[i];
}

else if(a[i] > second_max_element)
{
second_max_element = a[i];
}

}

so minimum no of comparision in worst case is 2 for one element so i think 63*2 = 126

#4

Think again @shreya.

According to the link of stackoverflow,

We can start comparing the elements pair wise and build a decision tree in which case it takes n-1 comparisons to obtain the highest element.

In order to get the second highest element we need to check only those elements which were compared with the highest element while building the decision tree, now as the height of the tree is logn and as logn comparisons are required for the highest element to reach the top, so to obtain second highest element one need logn-1 comparisons so all together (n - 1 + logn - 1) = (n + logn - 2) comparisons are required.

So, I think the answer should be = 64 + log64 - 2 (log is base 2) = 64 + 6 - 2 = 68.

#5

in worst case 94 comparisons are required.
algorithm:
[1,2,3,…64]
compare 1st two elements and store them in first_max,second_max
start the loop for remaining 62 elements

``````       Loop: every time take successive two elements A[i],A[i+1].
if(A[i]>A[i+1])
{
max = A[i]
max_2=A[i+1]
}
else{
max= A[i+1]
max_2=A[i]
}
if(first_max<max)
{
if(second_max<max_2){
second_max =max_2;
first_max      = max;
}
else{
second_max=first_max
first_max = max
}
}
else{
if(max>second_max)
second_max=max;
}
``````

in worst case for every two elements 3 comparisons are require and loop is iterated 62/2=31 times initially we do one comparison outside of the loop.
so total 1+3*62/2= 94
ans is 94

In other way there is a formula ::
for n elements 1+1.5*n comparisons are require to find the second second max or second min also.