Well you can avoid that condition by comparing the number by: 1. Keeping two numbers, largest and second largest. 2. Comparing with the second largest. If it is greater than the second largest, set second_largest = num. Else continue. 3. If second_largest > largest, swap(largest,second_largest).
O(n) complexity. Not sure, how to put a bound on the number of comparisons. On Sat, Sep 10, 2011 at 11:36 AM, abhinav gupta <[email protected]> wrote: > 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. > -- Gaurav Menghani -- 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.
