Search All of the Math Forum:

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

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

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

 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

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 Oluwa KuIse
9/19/08 stephanie
9/19/08 Steven Lord
9/19/08 Oluwa KuIse
9/19/08 Pekka
9/19/08 Oluwa KuIse
9/21/08 Greg Heath
9/24/08 Walter Roberson
3/4/09 Justin
4/6/09 Bruno Luong
4/6/09 Jos
4/6/09 Bruno Luong
4/6/09 Bruno Luong
4/6/09 mike zander
4/7/09 Bruno Luong
4/7/09 Bruno Luong
4/3/09 Paul
11/7/12 sssbi2009@gmail.com
11/19/12 dpb
4/3/09 Paul
4/3/09 mike zander
4/3/09 mike zander
4/3/09 mike zander
4/3/09 Walter Roberson
4/3/09 mike zander
5/4/13 tilindg1@gmail.com
5/4/13 Nasser Abbasi
5/4/13 dpb
5/5/13 Nasser Abbasi
5/5/13 dpb
5/5/13 Bruno Luong
5/5/13 Nasser Abbasi
5/5/13 Bruno Luong