Second largest

[Kelsey Bjarnason]

No, you're just unfamiliar with the the usage. N + O(log N) tells
you that the excess over N is O(log N).


That would be O(N + log(N)), which is not what we are talking about.

O(N + log(N)) doesn't mean anything different from O(N), but N + O(log N)
means something different and more precise.

Yeah, it means it's an O(N) algorithm with a completely irrelevant and
thus discounted log N side. Not to be confused with, say, O(N log N).

 

[Army1987]

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.)

 

[CBFalconer]

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.

 

[Kelsey Bjarnason]

[snips]

H_n = O(ln n)

... which says the nth harmonic number is approximately
proportional to the log of n. It might be a million
times the log of n, or it might be the log of n plus
a million; all we're told is that it's approximately
proportional, with an unknown proportionality constant
and unknown contributions from lower-order terms.

Correct, and this is the normal way to use such notation.

Consider the case where there is a "startup cost" of a million (eg it's
O(n)+1000000). Now determine the overhead when one item is involved...
when a thousand are involved... when a million are involved... when a
trillion are involved.

As the numbers increase, so too does the runtime, but the "startup cost"
remains constant. The algorithm is O(N); its runtime varies in proportion
to N, with the constant becoming insignificant as N increases.

Or your other example, of a million times the log of N. Again, as N
increases, the import of the million times the log of N decreases,
becoming totally insignificant for large N.

I suspect the disagreement here is over whether one is discussing this in
terms of algorithmic complexity, or actual "cost". In terms of
algorithmic complexity, the factor of the constant is irrelevant and
doesn't apply; in terms of actual cost, one needs to factor it in.

One might examine this in terms of doing something such as indexing large
amounts of data off a remote server, when the process requires caching the
data locally in order to index it: the algorithmic complexity determines
which indexing system to use, but the "startup cost" - the added constant
- determines the best way to get the data here and imposes a fundamental
limit to the performance of the operation regardless of algorithm
efficiency.

Back to programming: Can you explain why Quicksort
is usually said to be faster than Heapsort, even though both have
asymptotic average running times of O(n log n)? If you cannot, what
reason do you have to prefer one over the other?[*]

Because heap sort has a larger constant; for a given number of elements N,
quicksort runs faster than heapsort, all else being equal.

Both, of course, are O(n log n) algorithms, as opposed to O(n) or O(n^2),
although IIRC, quick sort is provably susceptible to O(n^2) degeneration.

[*] Assuming for simplicity's sake that your choice
is based solely on expected running time; there are, of course, many
other things an engineer must consider in an actual situation.

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.

 

[Eric Sosman]

Kelsey Bjarnason wrote On 08/05/07 16:41,:

[snips]

H_n = O(ln n)

... which says the nth harmonic number is approximately
proportional to the log of n. It might be a million
times the log of n, or it might be the log of n plus
a million; all we're told is that it's approximately
proportional, with an unknown proportionality constant
and unknown contributions from lower-order terms.

Correct, and this is the normal way to use such notation.

So Knuth *is* wrong? Be the first to tell him, and
collect your $2.56 bug reward. (Yes, he really does send
them out: I've got one. In a frame, which is where I
imagine most of them end up rather than back at the bank.)

Consider the case where there is a "startup cost" of a million (eg it's
O(n)+1000000). Now determine the overhead when one item is involved...
when a thousand are involved... when a million are involved... when a
trillion are involved.

As the numbers increase, so too does the runtime, but the "startup cost"
remains constant. The algorithm is O(N); its runtime varies in proportion
to N, with the constant becoming insignificant as N increases.

Or your other example, of a million times the log of N. Again, as N
increases, the import of the million times the log of N decreases,
becoming totally insignificant for large N.

I think you'd better re-examine this argument. One
million log N is larger than log N by an amount most
people would find significant. Yes, even (in fact,
especially) for very large N ...

I suspect the disagreement here is over whether one is discussing this in
terms of algorithmic complexity, or actual "cost". In terms of
algorithmic complexity, the factor of the constant is irrelevant and
doesn't apply; in terms of actual cost, one needs to factor it in.

One might examine this in terms of doing something such as indexing large
amounts of data off a remote server, when the process requires caching the
data locally in order to index it: the algorithmic complexity determines
which indexing system to use, but the "startup cost" - the added constant
- determines the best way to get the data here and imposes a fundamental
limit to the performance of the operation regardless of algorithm
efficiency.

Back to programming: Can you explain why Quicksort
is usually said to be faster than Heapsort, even though both have
asymptotic average running times of O(n log n)? If you cannot, what
reason do you have to prefer one over the other?[*]

Because heap sort has a larger constant; for a given number of elements N,
quicksort runs faster than heapsort, all else being equal.

... didn't you just finish saying that a factor of
a million is "irrelevant?" Yes, that's what you said --
so once again: On what grounds do you say Quicksort is
faster? (Mind you, I'm not saying that it isn't, and in
fact I think it is. But why do *you* think so, since a
factor of a million is "totally insignificant" and
"doesn't apply?")

Both, of course, are O(n log n) algorithms, as opposed to O(n) or O(n^2),
although IIRC, quick sort is provably susceptible to O(n^2) degeneration.

[*] Assuming for simplicity's sake that your choice
is based solely on expected running time; there are, of course, many
other things an engineer must consider in an actual situation.

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.

 

[Kelsey Bjarnason]

[snips]

So Knuth *is* wrong?

Wrong? Not in any absolutist sense. He's simply being overly
descriptive. There's nothing provably _wrong_ with adding details; it
just isn't how the notation is used conventionally.

Be the first to tell him, and
collect your $2.56 bug reward.

That wouldn't be a bug even if he were provably wrong; it would be, at
most, a documentation error.

I think you'd better re-examine this argument. One
million log N is larger than log N by an amount most people would find
significant. Yes, even (in fact, especially) for very large N ...

But it's proportional to N, it doesn't vary by log of N or by square of N,
it varies proportional to N. It's an O(N) algorithm, just an expensive
one.

... didn't you just finish saying that a factor of
a million is "irrelevant?"
Nope.

Yes, that's what you said

Read for context.

On what grounds do you say Quicksort is faster? (Mind you, I'm not
saying that it isn't, and in fact I think it is. But why do *you* think
so, since a factor of a million is "totally insignificant" and "doesn't
apply?")

Read for context.

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.

Let's take an example (and I'm still using base 10 values here, for sake
of simplicity): a program to sort a largish (1 million entry) phone book.

In normal circumstances, it takes N log N, or about 6 million operations.
Degenerating to O(N^2), it takes 1,000,000,000,000 operations, or about
167,000 times as long. If the O(N log N) operating takes two minutes, the
degenerate case takes some 231 days.

Now, as a developer, I'd tend to prefer a sort *not* take almost eight
months to complete, when it *should* take two minutes. Choosing a
different algorithm might mean it would take 5 minutes instead of two, but
as a tradeoff against never hitting an 8-month case, I suspect I - and the
customer - would prefer the five minute version.

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.

 

[CBFalconer]

.... big snip, discussing O notation, quicksort vs heapsort ...

... didn't you just finish saying that a factor of
a million is "irrelevant?" Yes, that's what you said --
so once again: On what grounds do you say Quicksort is
faster? (Mind you, I'm not saying that it isn't, and in
fact I think it is. But why do *you* think so, since a
factor of a million is "totally insignificant" and
"doesn't apply?")

Just take a look at the source for some simple implementations of
either, and compare the complexity of the inmost loop. Until the
awkward conditions (for O(N*N) in quicksort) showup, these control
the speed.

 

[santosh]

[snips]

Kelsey Bjarnason wrote:

[snip]

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.

 

[Eric Sosman]

Kelsey Bjarnason wrote On 08/06/07 13:31,:

[snips]

I think you'd better re-examine this argument. One
million log N is larger than log N by an amount most people would find
significant. Yes, even (in fact, especially) for very large N ...

But it's proportional to N, it doesn't vary by log of N or by square of N,
it varies proportional to N. It's an O(N) algorithm, just an expensive
one.

log N doesn't vary as log N?

log N is proportional to N?

I'm shocked speechless.

 

[Richard Harter]

[snips]

H_n = O(ln n)

... which says the nth harmonic number is approximately
proportional to the log of n. It might be a million
times the log of n, or it might be the log of n plus
a million; all we're told is that it's approximately
proportional, with an unknown proportionality constant
and unknown contributions from lower-order terms.

Correct, and this is the normal way to use such notation.

In simple words, you are wrong about what the convention is. It is
standard in mathematical works to write:

f(x) = g(x) + O(r(x))

where f(x) is some function, g(x) is an approximation to f(x), e(x) is the
error term, and r(x) is a bounding function for e(x). I repeat, this is
standard practice. Knuth is not wrong; Hamming is not wrong; the Handbook
of Mathematical functions is not wrong; you are wrong.

 

[user923005]

... didn't you just finish saying that a factor of
a million is "irrelevant?" Yes, that's what you said --
so once again: On what grounds do you say Quicksort is
faster? (Mind you, I'm not saying that it isn't, and in
fact I think it is. But why do *you* think so, since a
factor of a million is "totally insignificant" and
"doesn't apply?")

O(f(n)) is {roughly} defined as:
average time to completion is less than or equal to C * f(n) for some
constant C if n becomes 'large enough'.

For heapsort and quicksort, both are O(n*log(n)) but the C for
quicksort is smaller than the C for heapsort.

Hence, on average, quicksort takes less time than heapsort, given a
large enough input.

Of course, quicksort has degenerate cases that go O(n^2), but that is
neither here nor there and does not play into the argument.
[snip]

 

[Richard Bos]

Are you deliberately trying to create confusion?

No, I'm deliberately trying to insert some common sense.

Above I specified
(see the underlined area) "large values". These are not "expected
values" nor "mean values", etc. They are of unlimited size.

And that's my point. "Of unlimited size" is _not_ reality. It's
convention, mere convention. If it weren't, introspective sort wouldn't
work; quicksort is O(n log n), while insertion sort is O(n*n), and yet
introspective sort uses the fact that that O(n*n) has a minute constant.
Were "unlimited size" a reality, it could not.

Richard

 

[CBFalconer]

No, I'm deliberately trying to insert some common sense.


And that's my point. "Of unlimited size" is _not_ reality. It's
convention, mere convention. If it weren't, introspective sort wouldn't
work; quicksort is O(n log n), while insertion sort is O(n*n), and yet
introspective sort uses the fact that that O(n*n) has a minute constant.
Were "unlimited size" a reality, it could not.

That's not a point. Your attitude only works for some small
values. The O notation is expected to describe the performance
penalty variation with increasing size. It is general, yours is
specific.

 

[Kelsey Bjarnason]

Kelsey Bjarnason wrote On 08/06/07 13:31,:

[snips]

I think you'd better re-examine this argument. One
million log N is larger than log N by an amount most people would find
significant. Yes, even (in fact, especially) for very large N ...

But it's proportional to N, it doesn't vary by log of N or by square of
N, it varies proportional to N. It's an O(N) algorithm, just an
expensive one.

log N doesn't vary as log N?

Err... we were discussing an O(N) algorithm. If I misread a subsequent
insertion of a log, that's hardly something to get all shocked about.

 

[Kelsey Bjarnason]

[snips]

In simple words, you are wrong about what the convention is.

How odd. To date, virtually every reference I've ever read on the subject
uses them in exactly this way, even *explaining* them in exactly this way:
the dominant term is included, the rest are discarded, as they aren't
relevant to the algorithmic complexity.

I'm going to have to let at least 25 authors know they're all wrong, now, I
guess.

Bugger, and I was so hoping to actually relax this weekend.

 

[Richard Tobin]

How odd. To date, virtually every reference I've ever read on the subject
uses them in exactly this way, even *explaining* them in exactly this way:
the dominant term is included, the rest are discarded, as they aren't
relevant to the algorithmic complexity.

If the question was "what's the algorithmic complexity of whatever",
then you wouldn't answer "N + O(log N)". But that wasn't the
question. The question was to "use only N + O(log n) comparisons ...",
which is a perfectly clear and meaningful phrase and not in any way
a misuse of convention.

-- Richard

 

[Richard Bos]

That's not a point. Your attitude only works for some small
values. The O notation is expected to describe the performance
penalty variation with increasing size. It is general, yours is
specific.

But specific to most datasets occurring in practice.

Ah well, off to sort a card deck using heapsort. All in a day's work.

Richard

 

[Eric Sosman]

Kelsey Bjarnason wrote On 08/08/07 12:03,:

Kelsey Bjarnason wrote On 08/06/07 13:31,:

[snips]

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


I think you'd better re-examine this argument. One
million log N is larger than log N by an amount most people would find
significant. Yes, even (in fact, especially) for very large N ...


But it's proportional to N, it doesn't vary by log of N or by square of
N, it varies proportional to N. It's an O(N) algorithm, just an
expensive one.

log N doesn't vary as log N?

Err... we were discussing an O(N) algorithm. If I misread a subsequent
insertion of a log, that's hardly something to get all shocked about.

We were discussing Knuth's "misuse" of Big-O in

H_n = ln n + gamma + O(1/n)

.... and some of its possible simplifications

H_n = ln n + O(1)

H_n = O(log n)

I brought up the multiplicative factor of a million and
the additive constant of a million in connection with the
last of these, to point out that the successive versions
give less and less information. You responded that the
additive constant is irrelevant for sufficiently large n
(true) and that so was the coefficient (no, the importance
of the coefficient does not diminish with increasing n).

Perhaps our entire set-to has just been a confusion
about the subject matter, causing us to use the same words
with different referents. If so, I apologize for my heat,
and to atone for any offense I offer you ein Gift.

;-)

 

[Kelsey Bjarnason]

[snips]

Ah well, off to sort a card deck using heapsort. All in a day's work.

No, no. Use a bubble sort, just one with a small constant overhead per
item.

 

[Keith Thompson]

Perhaps our entire set-to has just been a confusion
about the subject matter, causing us to use the same words
with different referents. If so, I apologize for my heat,
and to atone for any offense I offer you ein Gift.

;-)

Um, do you know what "ein Gift" means in German?