sort it in quicksort (descending order)...den take arr[1] -->second largest
On Sat, Sep 10, 2011 at 8:34 AM, Akhilesh Vedhera <[email protected]>wrote: > Then the complexity will be nlogn not n.... and if it is the worst case > then it would be O(n^2)... > > On Sat, Sep 10, 2011 at 8:58 PM, abhinav gupta > <[email protected]>wrote: > >> Oops ..no u hav to quicksort it. >> >> >> On Sat, Sep 10, 2011 at 8:24 AM, Dave <[email protected]> wrote: >> >>> @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. >>> >>> >> >> >> -- >> @ |3 # ! /\/ @ \./ >> >> -- >> 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. >> > > > > -- > Akhilesh > NSIT-COE > > -- > 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 # ! /\/ @ \./ -- 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.
