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:


What is the answer @Adya_Nanda ?


#3

Lets start with 10 elements

max_element = a[0]
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.