@Replying to my own posting: remove the words "one of the numbers that lost to", so that the explanation reads
The question should be "How can we find the second largest element in an array in n + ceiling(log_2(n)) - 2 comparisons?" The answer is to use a tournament to select the largest number. The second largest number will have lost to the largest. It takes n - 1 comparisons to determine the largest number. There are ceiling(log_2(n)) numbers that have lost to the largest, and it takes ceiling(log_2(n)) - 1 comparisons to find the largest of them. Dave On Sep 10, 9:28 am, Dave <[email protected]> wrote: > @Praveen: The question should be "How can we find the second largest > element in an array in n + ceiling(log_2(n)) - 2 comparisons?" The > answer is to use a tournament to select the largest number. The second > largest number will have lost to one of the numbers that lost to the > largest. It takes n - 1 comparisons to determine the largest number. > There are ceiling(log_2(n)) numbers that have lost to the maximum, and > it takes ceiling(log_2(n)) - 1 comparisons to find the largest of > them. > > Dave > > On Sep 10, 9:18 am, praveen raj <[email protected]> wrote: > > > > > How can we find second largest element in an array... in O(n > > +logn-2)... give me proof.....- Hide quoted text - > > - Show quoted text - -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
