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 # ! /\/ @ \./
--
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.
