where n is the size of array
On Sat, Sep 10, 2011 at 9:16 PM, sukran dhawan <[email protected]>wrote:
>
>
> large1 = a[0];
> large2 = a[1];
>
>
> if(large1 < large2)
> swap(large1,large2)
>
> while(i < n)
> {
> if(a[i] > large1)
> {
> large2 = large1
> large1 = a[i]
> }
> else if(a[i] > large2)
> large2 = a[i]
> }
>
> // test the case if no of elements is 1 :)
>
>
> On Sat, Sep 10, 2011 at 8:54 PM, 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.
>>
>>
>
--
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.
