minimum number of comparison required to compute the largest and second largest element in an array is

Question

a) n- ( lg(n)) - 2

b) n + (lg(n)-2)

Answer 1

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

Comments

well the question asks for the exact  number of comparisons and not the asymptotic complexity, while building a heap AFAIK it takes different number of comparisons depending on the heap is built bottom up or top down. In neither case it is equal to the number of elements. Moreover the O(n) complexity of the heapify algorithm is a asymptotic result it does not show the exact number of comparisons required.

---

2n > n + lg n :)

I mean the complexity of the given algorithm is also O(n).

---

Sir, in second pass we need logn -1 comparisons. For that, we need to store all the numbers being compared with max element. Now, initially we don't know the max element. So do we end up storing all the elements with which a particular element is compared with, for all the elements in the list ? We can make a binary tree for that but it will require additional space. Can we do it in any better way?

And about the heap, what will be the worst case number of comparisons when building the heap using bottom up approach ? The comparisons will surely be greater than n according to me.

So for building heap, >n comparisons. After finding first maximum, logn comparisons for heapify and then we can get 2nd element. So total number of comparisons using heap will be > n+logn. Am I correct?