@shishir can u give the ds how would u save the history part ("save the data that was rejected by the highest element in order to get the 2nd highest")
extra space will b required.. :( On Mon, Oct 12, 2009 at 3:15 AM, Shishir Mittal <1987.shis...@gmail.com>wrote: > It has been discussed here > http://groups.google.com/group/algogeeks/browse_thread/thread/5a3ccc1bfb4617fa/885438e251ffd330?lnk=gst&q=second+highest+element#885438e251ffd330 > > On Sun, Oct 11, 2009 at 8:21 PM, Manisha <pgo...@gmail.com> wrote: > >> >> First find out the largest element and it requires n-1 comparison. >> Lets say we have 8 elements then we need 7 comparison to decide >> largest. Imagine the tree structure that you will use to find out >> largest. >> 21 >> 15 21 >> 9 15 8 21 >> 2 9 11 15 7 8 9 21 >> >> Notice that second largest will be be smaller than largest and larger >> than any other item in the list. So it is sure that second largest >> will loose in comparison with largest. Hence Second largest will be >> searched only with the items that got compared with largest item. >> Number of items that got compared with largest is logn(height of >> tree). >> logn-1 comparison is needed to find largest among them. >> >> Total comparison to find second largest = (n-1) + (logn-1) >> >> >> On Oct 10, 11:52 pm, sankalp <sankalpmishr...@gmail.com> wrote: >> > can anyone give me algorithm for finding the second largest element in >> > array using tournament method requiring n+logn-2 compariso >> >> >> > > > -- > Shishir Mittal > Ph: +91 9936 180 121 > > > > > --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@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 -~----------~----~----~----~------~----~------~--~---