temp2 is second largest element.
On Sat, Sep 10, 2011 at 8:00 AM, abhinav gupta <guptaabhinav...@gmail.com>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 <dave_and_da...@juno.com> 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 <dave_and_da...@juno.com> 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 <praveen0...@gmail.com> 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 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?hl=en.
>>
>>
>
>
> --
> @ |3 # ! /\/ @ \./
>
--
@ |3 # ! /\/ @ \./
--
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?hl=en.
