
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 lineartime 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 10001.12703739213806 10^41.33 10^51.36 10^61.67 10^72.2

