@Abhinav: Does it work correctly on {1, 3, 2}, or, for that matter, on
any array where the second largest comes after the largest?Dave On Sep 10, 10:16 am, abhinav gupta <[email protected]> wrote: > temp2 is second largest element. > > On Sat, Sep 10, 2011 at 8:00 AM, abhinav gupta > <[email protected]>wrote: > > > > > > > I can solve this problem in O(n) > > i=0; > > temp1=arr[0]; > > > while(i != len) > > { > > if(arr[i] > temp1) > > { > > temp2=temp1; > > temp1=arr[i] > > } > > i++; > > } > > > On Sat, Sep 10, 2011 at 7:42 AM, Dave <[email protected]> wrote: > > >> @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. > > > -- > > @ |3 # ! /\/ @ \./ > > -- > @ |3 # ! /\/ @ \./- 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.
