Do a single-elimination tournament of the numbers, where the larger wins each "game". This will take n/2 + n/4 + ... + 1 <= n-1 comparisons. The second largest will be among the numbers that lost to the largest in one of the "games". As you conduct the tournament, keep track of the losers. Since there will be at most ceiling(log_2(n)) stages in the tournament, you can find the largest of the losers to the winner in ceiling(log_2(n))-1 comparisons.
Dave On Sep 23, 1:36 pm, Divesh Dixit <dixit.coolfrog.div...@gmail.com> wrote: > finding largest and second largest elements from a set of n elements > by means of > Minimum comparison of n+celling(log n) +2.... -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
