Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

Views expressed in these public forums are not endorsed by Drexel University or The Math Forum.


Math Forum » Discussions » Software » comp.soft-sys.matlab

Topic: second largest element in a matrix
Replies: 32   Last Post: May 5, 2013 10:31 AM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
mike zander

Posts: 3,542
Registered: 11/29/05
Re: second largest element in a matrix
Posted: Apr 3, 2009 11:28 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

Walter Roberson <roberson@hushmail.com> wrote in message <qbABl.1289$0%2.625@newsfe22.iad>...

> Depends on the matrix sizes. max() is an order(N) operation. sort is something like
> order (N*log(N)). With large matrices, two linear passes through the matrix would be
> considerably faster than a sort().
>
> Note: in previous postings, someone posted a reference to a linear-time routine
> to find the "Q largest" values in a vector; that code would only pass through the
> matrix once (but might make up to Q comparisons at each point in order to establish
> the proper ordering.)



True enough, but I was accounting for the copy time in the comparisons I made (apples to apples ---> We start with a vector and end with the vector intact plus the second largest value and its index.)
Nevertheless my timings show you are correct. The relative speed of the approach shown above increases as N gets larger and larger.

N -------------- tsort/tnan
1000--------1.12703739213806
10^4--------1.33
10^5--------1.36
10^6--------1.67
10^7--------2.2


Date Subject Author
9/18/08
Read second largest element in a matrix
Oluwa KuIse
9/19/08
Read Re: second largest element in a matrix
stephanie
9/19/08
Read Re: second largest element in a matrix
Steven Lord
9/19/08
Read Re: second largest element in a matrix
Oluwa KuIse
9/19/08
Read Re: second largest element in a matrix
Pekka
9/19/08
Read Re: second largest element in a matrix
Oluwa KuIse
9/21/08
Read Re: second largest element in a matrix
Greg Heath
9/24/08
Read Re: second largest element in a matrix
Walter Roberson
3/4/09
Read Re: second largest element in a matrix
Justin
4/6/09
Read Re: second largest element in a matrix
Bruno Luong
4/6/09
Read Re: second largest element in a matrix
Jos
4/6/09
Read Re: second largest element in a matrix
Bruno Luong
4/6/09
Read Re: second largest element in a matrix
Bruno Luong
4/6/09
Read Re: second largest element in a matrix
mike zander
4/7/09
Read Re: second largest element in a matrix
Bruno Luong
4/7/09
Read Re: second largest element in a matrix
Bruno Luong
4/3/09
Read Re: second largest element in a matrix
Paul
11/7/12
Read Re: second largest element in a matrix
sssbi2009@gmail.com
11/19/12
Read Re: second largest element in a matrix
dpb
4/3/09
Read Re: second largest element in a matrix
Paul
4/3/09
Read Re: second largest element in a matrix
mike zander
4/3/09
Read Re: second largest element in a matrix
mike zander
4/3/09
Read Re: second largest element in a matrix
mike zander
4/3/09
Read Re: second largest element in a matrix
Walter Roberson
4/3/09
Read Re: second largest element in a matrix
mike zander
5/4/13
Read Re: second largest element in a matrix
tilindg1@gmail.com
5/4/13
Read Re: second largest element in a matrix
Nasser Abbasi
5/4/13
Read Re: second largest element in a matrix
dpb
5/5/13
Read Re: second largest element in a matrix
Nasser Abbasi
5/5/13
Read Re: second largest element in a matrix
dpb
5/5/13
Read Re: second largest element in a matrix
Bruno Luong
5/5/13
Read Re: second largest element in a matrix
Nasser Abbasi
5/5/13
Read Re: second largest element in a matrix
Bruno Luong

Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.