Second largest

[ravi]

Can anybody tell me a method to

Use only N + O(log n) comparisons to find the second largest (or
smallest) element in a list of N elements.

Thnx in advance

[Richard Bos]

CBFalconer <cb********@yah oo.comwrote:

Kelsey Bjarnason wrote:

Convention is to count only the most significant factor; thus an
algorithm which runs in O(N) + 1000 time is an O(N) algorithm, the
constant is discarded.

In the description above, the function should run in N + O(log N)
time. As N increases, runtime increases in proportion to it, with
log N adding a small and ever less significant portion of the
runtime; thus the O(log n) is discarded and the algorithm is thus
found to be O(N).

It's not a convention, it's reality. The technique is intended to
describe execution time required for large values of N. For large
enough N the value of log N is negligible, compared to N, and is
thus discarded.

No, it's convention. Reality is that a function which is X*O(N) +
Y*O(log N) tends to O(N) or to O(log N), depending on the relative sizes
of X and Y, for reasonable N. O(N) only dominates the time for _all_ X
if you go to Microsoft-sales-figures values of N. For most of us, such
an algorithm is O(N) if X is large relative to Y, and O(log N) if X is
small compared to Y. Assuming that N will always tend to be large enough
to dominate both X and Y, that _is_ mere convention.
(For example: even though it is by convention O(N), an algorithm which
runs through an array once, to determine maximum and minimum values, and
then performs an O(log N) operation on it quickly using those values,
can be faster for all data sets which occur in reality than an algorithm
which is also O(log N), but which runs slower because it doesn't use the
min/max values.)

Richard

[Richard Tobin]

In article <c4************ @spanky.localho st.net>,
Kelsey Bjarnason <kb********@gma il.comwrote:

>What's wrong with N + O(log N) (assuming the n should be N)? It has a
perfectly well-defined meaning, that if you subtract N from the number
of comparisons, the result is O(log N).

>Convention is to count only the most significant factor; thus an algorithm
which runs in O(N) + 1000 time is an O(N) algorithm, the constant is
discarded.

In the description above, the function should run in N + O(log N) time.
As N increases, runtime increases in proportion to it, with log N adding a
small and ever less significant portion of the runtime; thus the O(log
n) is discarded and the algorithm is thus found to be O(N).

I'm not sure whether you're disagreeing with me or not...

An algorithm that does N + O(log N) comparisons does indeed do O(N)
comparisons, but the former statement is more precise. There are
algorithms that do O(N) comparisons but more than N + O(log N), for
example one that does 2N.

-- Richard
--
"Considerat ion shall be given to the need for as many as 32 characters
in some alphabets" - X3.4, 1963.

[Spoon]

ravi wrote:

Use only N + O(log N) comparisons to find the second largest
(or smallest) element in a list of N elements.

You're in the wrong newsgroup. (I think you want comp.programmin g)
http://en.wikipedia.org/wiki/Selection_algorithm

[Spoon]

Army1987 wrote:

if (a - b - abs(a - b))
/* a is greater than or equal to b */;
else
/* a is smaller than b */;

so you can do anything with 0 comparisons.

How do you suppose abs() is defined?

[Richard Heathfield]

Spoon said:

Army1987 wrote:

>if (a - b - abs(a - b))
/* a is greater than or equal to b */;
else
/* a is smaller than b */;

so you can do anything with 0 comparisons.

How do you suppose abs() is defined?

As a function that takes ints, not elements (whereas the OP specifically
asked for elements, not necessarily ints, from which we may assume that
the OP is after a general solution).

Another objection to the above is the behaviour when a - b < INT_MIN.

--
Richard Heathfield <http://www.cpax.org.uk >
Email: -www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999

[Army1987]

On Fri, 03 Aug 2007 13:38:20 +0200, Spoon wrote:

Army1987 wrote:

>if (a - b - abs(a - b))
/* a is greater than or equal to b */;
else
/* a is smaller than b */;

so you can do anything with 0 comparisons.

How do you suppose abs() is defined?

I don't think anything in the Standard forbids it to be defined
like
int abs(int _n)
{
long double _x = n * n;
return (int)nearbyintl (sqrtl(_x));
}
provided that long double has enough precision. I don't think it
is actually implemented like that anywhere, but you can always
write your own function which does that. :-)

--
Army1987 (Replace "NOSPAM" with "email")
"Never attribute to malice that which can be adequately explained
by stupidity." -- R. J. Hanlon (?)

[CBFalconer]

Richard Bos wrote:

CBFalconer <cb********@yah oo.comwrote:

.... snip ...

>

>It's not a convention, it's reality. The technique is intended to
describe execution time required for large values of N. For large

^^^^^^^^^^^^

>enough N the value of log N is negligible, compared to N, and is
thus discarded.

No, it's convention. Reality is that a function which is X*O(N) +
Y*O(log N) tends to O(N) or to O(log N), depending on the relative sizes
of X and Y, for reasonable N. O(N) only dominates the time for _all_ X

....

Are you deliberately trying to create confusion? Above I specified
(see the underlined area) "large values". These are not "expected
values" nor "mean values", etc. They are of unlimited size. If
you don't like a size, go bigger. In the particular example, for
large N, log N becomes negligible when compared to N.

--
"Vista is finally secure from hacking. No one is going to 'hack'
the product activation and try and steal the o/s. Anyone smart
enough to do so is also smart enough not to want to bother."

--
Posted via a free Usenet account from http://www.teranews.com

[Army1987]

On Fri, 03 Aug 2007 15:41:54 -0400, CBFalconer wrote:

--
"Vista is finally secure from hacking. No one is going to 'hack'
the product activation and try and steal the o/s. Anyone smart
enough to do so is also smart enough not to want to bother."

Where did you get that quote?
(And unfortunately a future in which people smart enough to do that
will want to bother because somebody pays them to do so doesn't
seem that unlikely.)

(I only used Vista once or twice, to try to solve a problem a
friend of mine was having. Both times I gave up and the second
time I kind of asked him to get lost until he stopped using it.)
--
Army1987 (Replace "NOSPAM" with "email")
"Never attribute to malice that which can be adequately explained
by stupidity." -- R. J. Hanlon (?)

[CBFalconer]

Army1987 wrote:

On Fri, 03 Aug 2007 15:41:54 -0400, CBFalconer wrote:

>"Vista is finally secure from hacking. No one is going to 'hack'
the product activation and try and steal the o/s. Anyone smart
enough to do so is also smart enough not to want to bother."

Where did you get that quote?

>From someone in some Linux group. I acknowledged the theft at the

time, but forget where I stole it.

--
"Vista is finally secure from hacking. No one is going to 'hack'
the product activation and try and steal the o/s. Anyone smart
enough to do so is also smart enough not to want to bother."
--
Posted via a free Usenet account from http://www.teranews.com

[santosh]

Kelsey Bjarnason wrote:

[snips]

On Mon, 06 Aug 2007 10:36:04 -0400, Eric Sosman wrote:

>Kelsey Bjarnason wrote:

[snip]

>>If my choice is expected running time, I'd have to choose heapsort, as
its worst case is O(n log n), unless I'm working with sufficiently
small, or sufficiently well-defined data sets that O(n^2) degeneration
doesn't affect the outcome significantly enough to matter, or it can be
proven that quicksort can be designed to avoid degenerate behaviour in
all cases.

If the choice is based on *expected* running time, then
you'd be making the wrong choice. Worst-case running time is a
different criterion.

On the contrary. *Expected* run time *includes* worst case, unless you
can guarantee non-degenerate data sets. Since you can't do that in most
cases, you *expect* to run across them at least occasionally.

[ ... ]

Maybe that degenerate case only happens one in a thousand runs... but
considering the scope of the failure when it does happen, even odds like
that make it worth using the slightly less efficient algorithm which
doesn't degenerate.

Or you could always use an hybrid algorithm that switches according to
runtime behaviour.