Benchmarks

[s0suk3]

The task: Write a program that reads a set of words from standard
input and prints the number of distinct words.

I came across a website that listed a few programs to accomplish this
task: http://unthought.net/c++/c_vs_c++.html (ignore all the language
flaming :-), and thought that all of them did unnecessary operations,
so I wrote my own. But for some reason, my version turned out slower
that ALL of the versions in the website, even though it seems to
perform less operations (yes, I benchmarked them on my own computer).

According to the website, the slowest version is:

#include <set>
#include <string>
#include <iostream>

int main(int argc, char **argv)
{
// Declare and Initialize some variables
std::string word;
std::set<std::stringwordcount;
// Read words and insert in rb-tree
while (std::cin >word) wordcount.insert(word);
// Print the result
std::cout << "Words: " << wordcount.size() << std::endl;
return 0;
}

My version is about 12 times slower than that. It uses lower-level
constructs. Here it is:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

struct SetNode
{
char *word;
struct SetNode *next;
};

// An unorderd set of words
//
static struct SetNode *gSet = 0;
static int gSetSize = 0;

#define kInitWordSize 32

// Returns a word read from stdin. The returned pointer must be
// deallocated with free().
//
static char *
ReadOneWord(void)
{
int ch = getchar();

while (ch != EOF && isspace(ch))
ch = getchar();
if (ch == EOF)
return 0;

char *word = (char *) malloc(kInitWordSize);
if (!word)
return 0;

int size = kInitWordSize;
int i = 0;

while (ch != EOF && !isspace(ch)) {
if (i >= size) {
size *= 2;

char *newWord = (char *) realloc(word, size);
if (!newWord) {
free(word);
return 0;
}
word = newWord;
}

word[i++] = ch;
ch = getchar();
}

if (i >= size) {
size *= 2;

char *newWord = (char *) realloc(word, size);
if (!newWord) {
free(word);
return 0;
}
word = newWord;
}
word[i] = '\0';

return word;
}

// Inserts a word into the set if it isn't in the set.
// The passed string is expected to have been allocated with
// a memory allocation function, and it should be considered
// lost after passed to this function.
//
static void
InsertWord(char *aWord)
{
struct SetNode *node;

for (node = gSet; node; node = node->next) {
if (strcmp(node->word, aWord) == 0) {
free(aWord);
return;
}
}

node = (struct SetNode *) malloc(sizeof(struct SetNode));
if (!node) {
free(aWord);
return;
}

node->word = aWord;
node->next = gSet;
gSet = node;
++gSetSize;
}

static void
DeleteSet(void)
{
struct SetNode *node = gSet;
struct SetNode *temp;

while (node) {
temp = node;
node = node->next;
free(temp->word);
free(temp);
}

gSet = 0;
gSetSize = 0;
}

int
main(void)
{
char *word;

while ((word = ReadOneWord()))
InsertWord(word);

printf("Words: %d\n", gSetSize);

// Skip cleanup for now...
//DeleteSet();
}

Any ideas as to what causes the big slowdown?

Sebastian

[Kai-Uwe Bux]

Jerry Coffin wrote:

In article <49***************@yahoo.com>, cb********@yahoo.com says...

[ ... ]

>The result is that for most cases quicksort will be the fastest
sort. Right behind it are other O(nLOGn) methods. I prefer
mergesort and data input in lists, because then I don't have to
worry about the size to be sorted. In addition, mergesort is
stable (quicksort is not).

The most common implementation of Quicksort for arrays is unstable --
but a Quicksort on an array _can_ be written to be stable if you want to
badly enough, and for a linked list, it's quite easy to make it stable.

My linguistic intuitions differ: Quicksort _is_ the algorithm published as
Algorithm 64 (and 63) by C.A.R. Hoare in the Communications of the ACM.
That algorithm sorts a sequence in place and is not stable. It makes
2n*log(n) comparisons on average and (1/3)n*log(n) exchanges on average.
Anything that is stable or deals with linked lists is an implementation of
a _different_ algorithm (and probably has different average complexities).

I am not saying that there are no refinements or other algorithms based on
similar ideas. Some of these algorithms are stable and some apply to linked
lists. Also, I am not a native speaker of English. Nonetheless, I feel that
algorithms have a certain identity (which makes it meaningfull to say that
a certain sorting algorithm is stable); and that implementations of an
algorithm must preserve that identity and the associated characteristics to
count as implementations _of_ that algorithm.
Best

Kai-Uwe Bux

[Juha Nieminen]

Kai-Uwe Bux wrote:

Big-O notation is oblivious to whether it is used to say something about the
worst case or about the average case. It also does not care whether you say
something about time or space complexity. In fact, Big-O is a purely
mathematical concept: Given two functions f and g, we say that f is a
O(g) if there is a constant C such that f(x) <= C g(x) for all x.

For computer science, f is often the worst case runtime of an algorithm
depending on some input length n (in some measure). So, we say that this
algorithm has worst case time complexity O(n^2) if the worst case run time
is bounded from above by C n^2 for some C. However, f could be the
average runtime or it could be the worst case space complexity, or some
other function. Thus, you can use Big-O notation also to say something
about worst case space complexity, average case time complexity, or other
complexities. The Big-O won't care.

You talk about the big-O notation as some kind of generic function
which describes some asymptotic behavior of an algorithm. Basically you
are implying that the big-O notation could be used to describe *any*
asymptotic behavior of an algorithm. In other words, you could say
something like "insertion sort is O(n) in the best case".

If that is what you mean, then you will have a hard time explaining
what's the difference between the big-O notation, the big-Omega notation
and the big-Theta notation.

Where the big-O notation denotes the upper bound of the asymptotic
behavior of an algorithm, the big-Omega notation likewise denotes the
lower bound. In other words, the asymptotic behavior of an algorithm is
always between these two functions. For example insertion sort is O(n^2)
and Omega(n): Its worst case scenario performs quadratically with
respect to the size of the input, while its best case scenario behaves
linearly.

When the big-O and big-Omega functions for an algorithm are the same,
this can be expressed with the big-Theta function, which says exactly
that. In other words, it says that both the upper and the lower bounds
of the asymptotic behavior of the algorithm are the same. For example
merge sort is Theta(n lg n): It's O(n lg n) and Omega(n lg n).

You just can't say "quicksort is O(n lg n)" because that would be a
lie. The worst case scenario for quicksort is n^2, thus saying that it's
O(n lg n) is wrong.

AFAIK there's no widely established asymptotic notation for the
average behavior of a function, but if you want to express that, you'll
have to say it more verbosely. Sure, you can use a shortcut and say
"quicksort is O(n lg n) in average", but that would be technically
incorrect, or at least quite informal.

[Juha Nieminen]

CBFalconer wrote:

>For example quicksort is O(n^2). (Don't believe what people say.
It *is* O(n^2), period.)

I suspect you know what you are talking about, but you are leaving
the wrong impression. The sort of sequence that produces O(n*n)
quicksort performance is extremely rare, and very slight controls
make it even rarer (such as selecting the median of 3 items as the
value to partition about).

The purpose of the big-O notation is not to tell how well an algorithm
behaves in average or in most cases. It's a pure upper bound to the
asymptotic behavior of the algorithm.

Of course if we get completely technical, the big-O notation assumes
that the input can have any size. If you put an upper limit to the size
of the input (for example an amount relative to the amount of memory
addressable by the CPU, eg. 2^64 bytes), all algorithms which end at
some point (ie. don't go into an infinite loop) immediately become O(1).

Of course saying "all terminating algorithms are O(1) in my computer"
is not very informative, which is why it's always implicitly assumed
that there is no set limit.

[Juha Nieminen]

Kai-Uwe Bux wrote:

My linguistic intuitions differ: Quicksort _is_ the algorithm published as
Algorithm 64 (and 63) by C.A.R. Hoare in the Communications of the ACM.
That algorithm sorts a sequence in place and is not stable. It makes
2n*log(n) comparisons on average and (1/3)n*log(n) exchanges on average.
Anything that is stable or deals with linked lists is an implementation of
a _different_ algorithm (and probably has different average complexities).

Why? Although it's a surprisingly common misconception that quicksort
requires random access, it doesn't. Quicksort is implemented in terms of
purely linear traversals of the array. Thus it's perfectly possible to
implement the *exact* same algorithm for a doubly-linked list (which can
be traversed forwards and backwards).

[Juha Nieminen]

Richard Harter wrote:

As others have pointed out, this is seriously misinformed. This
bit of folklore pops up every once in a while. Where does it
come from?

No, what is folklore is the custom of using the big-O notation to
describe *all* possible asymptotic behaviors of an algorithm. While that
may work colloquially, it's technically incorrect.

The big-O notation specifies the asymptotic upper bound for the
behavior of the algorithm. It does not specify anything else.

If the big-O notation could be used to describe *any* asymptotic
behavior for a given algorithm, then please explain to me how it differs
from the big-Omega and big-Theta notations. Wouldn't the big-O make
those obsolete?

[Juha Nieminen]

James Kanze wrote:

On Nov 8, 12:27 am, user923005 <[e-mail]:

>On Nov 7, 2:47 pm, Juha Nieminen <[e-mail]:
Sure. If hash(x) == return 1; then bad behavior is to be
expected. The assumption is of maximally cascade free hash
functions like UMAC or Bob Jenkin's hash.

Do you have any references on those, particularly with an
implementation? All I found for UMAC was a reference to book,
and Bob Jenkin's seems more concerned with cryptographic hashing
than anything else. If these are standard and widely used
algorithms for look-up hashing, I'd like to add them to my set
of hashing benchmarks.

(Note that cryptographic hashing and look-up hashing have very
different constraints, and a good hash function for one isn't
necessarily a good hash function for the other. Also, in
look-up hashing, speed counts. Taking 10 times more time to get
1% better distribution on the average is a loss.)

I'm pretty sure Jenkin's hashing function (which uses the same
algorithm as his ISAAC random number generator) is faster than anything
you could ever create yourself, having even a fraction of the same quality.

[Andre Kostur]

Juha Nieminen <no****@thanks.invalidwrote in news:64%Rk.149$O41.3
@read4.inet.fi:

CBFalconer wrote:

>>For example quicksort is O(n^2). (Don't believe what people say.
It *is* O(n^2), period.)

I suspect you know what you are talking about, but you are leaving
the wrong impression. The sort of sequence that produces O(n*n)
quicksort performance is extremely rare, and very slight controls
make it even rarer (such as selecting the median of 3 items as the
value to partition about).

The purpose of the big-O notation is not to tell how well an algorithm
behaves in average or in most cases. It's a pure upper bound to the
asymptotic behavior of the algorithm.

Not necessarily true. The big-O could refer to best-case, average, worst-
case, or anything in between. You just need to specify it. As I recall,
quicksort is O(n lg n) in the average case, O(n^2) worst case. Both say
something interesting about the algorithm.

[Juha Nieminen]

Andre Kostur wrote:

Not necessarily true. The big-O could refer to best-case, average, worst-
case, or anything in between. You just need to specify it. As I recall,
quicksort is O(n lg n) in the average case, O(n^2) worst case. Both say
something interesting about the algorithm.

While you can say that colloquially, it's formally quite shaky.

In computational complexity theory big-O is not a generic notation
used to describe some asymptotic behavior of an algorithm. It's used to
specify an upper bound to the asymptotic behavior of an algorithm.

Saying, for example, "insertion sort is O(2^n)" is completely valid.
O(n^100) is equally valid. The big-O notation does not even require for
the upper bound to be tight. Any upper bound is valid as long as the
algorithm never behaves slower than that. However, saying "insertion
sort is O(n)" is not valid because with some inputs insertion sort
performs asymptotically more steps than that.

Even if you say "quicksort is O(n lg n) in average", the upper bound
is still not correct. Even when measuring average behavior quicksort
will behave slower than (n lg n) with some inputs, and thus the given
upper bound is incorrect.

Likewise the big-Omega notation is used to set a lower bound to the
asymptotic behavior of an algorithm. For example if you say "insertion
sort is Omega(n)", you are telling that insertion sort never performs
less steps than an amount linearly relative to the size of the input.

Saying "the best case for insertion sort is O(n)" is exactly as silly
as saying "the worst case for insertion sort is Omega(n^2)". They don't
make sense as bounds in these sentences. They are misused to describe
some special cases.

[Pete Becker]

On 2008-11-10 14:43:06 -0500, Juha Nieminen <no****@thanks.invalidsaid:

Even if you say "quicksort is O(n lg n) in average", the upper bound
is still not correct. Even when measuring average behavior quicksort
will behave slower than (n lg n) with some inputs, and thus the given
upper bound is incorrect.

You can't ignore the qualifier "on average", which implies some
constraints on input sequences. Yes, it's O(n^2) for some input
sequences, but if you rule out those input sequences, then it's
O(nlogn), and that's all that "on average" means. Big-oh notation tells
you what happens when the input sequence gets long. It doesn't tell you
anything about the contents of input sequences.

--
Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com) Author of "The
Standard C++ Library Extensions: a Tutorial and Reference
(www.petebecker.com/tr1book)

[Ben Bacarisse]

Juha Nieminen <no****@thanks.invalidwrites:

Kai-Uwe Bux wrote:

>Big-O notation is oblivious to whether it is used to say something about the
worst case or about the average case. It also does not care whether you say
something about time or space complexity. In fact, Big-O is a purely
mathematical concept: Given two functions f and g, we say that f is a
O(g) if there is a constant C such that f(x) <= C g(x) for all x.

For computer science, f is often the worst case runtime of an algorithm
depending on some input length n (in some measure). So, we say that this
algorithm has worst case time complexity O(n^2) if the worst case run time
is bounded from above by C n^2 for some C. However, f could be the
average runtime or it could be the worst case space complexity, or some
other function. Thus, you can use Big-O notation also to say something
about worst case space complexity, average case time complexity, or other
complexities. The Big-O won't care.

You talk about the big-O notation as some kind of generic function
which describes some asymptotic behavior of an algorithm. Basically you
are implying that the big-O notation could be used to describe *any*
asymptotic behavior of an algorithm. In other words, you could say
something like "insertion sort is O(n) in the best case".

Yes one can do that, if you specify all the terms. I don't know why
one would, but it is certainly possible.

If that is what you mean, then you will have a hard time explaining
what's the difference between the big-O notation, the big-Omega notation
and the big-Theta notation.

I can't see the problem. These notions express facts about functions
-- specifically membership of certain equivalence classes. If the
functions are properly defined, then so are the classes to which they
belong.

Where the big-O notation denotes the upper bound of the asymptotic
behavior of an algorithm, the big-Omega notation likewise denotes the
lower bound.

Using this terminology will cause trouble. In fact it may be the main
cause of the trouble. First. Big-O gives *an* upper bound, not *the*
upper bound (and certainly not the least upper bound). Secondly, you
can't apply the notation to an algorithm, only to some function
derived from the algorithm.

I get the feeling that you don't like it when that function is "the
average time taken over all possible inputs of size N" but that
measure is often useful. That function, for Quicksort, is O(n log n)
when all the details are formalised.

In other words, the asymptotic behavior of an algorithm is
always between these two functions. For example insertion sort is O(n^2)
and Omega(n): Its worst case scenario performs quadratically with
respect to the size of the input, while its best case scenario behaves
linearly.

This is not helpful. Its time complexity is also O(n^3) and Omega(1).

When the big-O and big-Omega functions for an algorithm are the same,
this can be expressed with the big-Theta function, which says exactly
that.

You can't talk about an algorithm's big-O and big-Omega. Even if the
quantity in question is specified (e.g. worst-case time, average
space used, and so on) every algorithm has an unlimited number of
big-O bounds on that quantity.

In other words, it says that both the upper and the lower bounds
of the asymptotic behavior of the algorithm are the same. For example
merge sort is Theta(n lg n): It's O(n lg n) and Omega(n lg n).

But the time complexity for merge sort is also O(n^2). The key fact
is that if the function in question (say "longest time taken for data
of size N") is both O(f) and Omega(f) we say it is Theta(f). There is
no need to pretend that there is only one Big-O for the algorithm and
then go check if it is also the one and only Big-Omega for the
algorithm.

You just can't say "quicksort is O(n lg n)" because that would be a
lie. The worst case scenario for quicksort is n^2, thus saying that it's
O(n lg n) is wrong.

I agree, but did anyone say that (I have not checked)?

AFAIK there's no widely established asymptotic notation for the
average behavior of a function,

I disagree. I think the notion is well-defined and accepted by people
who study such things.

but if you want to express that, you'll
have to say it more verbosely. Sure, you can use a shortcut and say
"quicksort is O(n lg n) in average", but that would be technically
incorrect, or at least quite informal.

Saying "quicksort is O(n lg n) in average" is certainly very informal,
but so it saying that is "is O(n^2)". Both can be properly formalised.

--
Ben.

[Tim Rentsch]

Juha Nieminen <no****@thanks.invalidwrites:

Kai-Uwe Bux wrote:

My linguistic intuitions differ: Quicksort _is_ the algorithm published as
Algorithm 64 (and 63) by C.A.R. Hoare in the Communications of the ACM.
That algorithm sorts a sequence in place and is not stable. It makes
2n*log(n) comparisons on average and (1/3)n*log(n) exchanges on average.
Anything that is stable or deals with linked lists is an implementation of
a _different_ algorithm (and probably has different average complexities).

Why? Although it's a surprisingly common misconception that quicksort
requires random access, it doesn't. Quicksort is implemented in terms of
purely linear traversals of the array. Thus it's perfectly possible to
implement the *exact* same algorithm for a doubly-linked list (which can
be traversed forwards and backwards).

Are you sure you understand what the term "stable" means for
sort algorithms, and why Quicksort isn't stable? The various
Quicksort algorithms I'm familiar with simply are not stable,
regardless of whether the elements to be sorted are held in
an array or in a doubly linked list.

[Tim Rentsch]

Juha Nieminen <no****@thanks.invalidwrites:

Richard Harter wrote:

As others have pointed out, this is seriously misinformed. This
bit of folklore pops up every once in a while. Where does it
come from?

No, what is folklore is the custom of using the big-O notation to
describe *all* possible asymptotic behaviors of an algorithm. While that
may work colloquially, it's technically incorrect.

The big-O notation specifies the asymptotic upper bound for the
behavior of the algorithm. It does not specify anything else.

If the big-O notation could be used to describe *any* asymptotic
behavior for a given algorithm, then please explain to me how it differs
from the big-Omega and big-Theta notations. Wouldn't the big-O make
those obsolete?

http://en.wikipedia.org/wiki/Big_O_notation

Big-O notation is used to describe the asymptotic behavior of
functions, not algorithms. The worst case run time of an
algorithm, in terms of the size of its input, is one such
function; the average case run time of an algorithm is
another such function. Informally people say things like
"a bubble sort is O(n**2)", but really what is O(n**2)
is a function giving the running time of the algorithm,
not the algorithm itself.

[Richard Harter]

On Mon, 10 Nov 2008 18:36:00 GMT, Juha Nieminen
<no****@thanks.invalidwrote:

>Richard Harter wrote:

>As others have pointed out, this is seriously misinformed. This
bit of folklore pops up every once in a while. Where does it
come from?

No, what is folklore is the custom of using the big-O notation to
describe *all* possible asymptotic behaviors of an algorithm. While that
may work colloquially, it's technically incorrect.

The big-O notation specifies the asymptotic upper bound for the
behavior of the algorithm. It does not specify anything else.

If the big-O notation could be used to describe *any* asymptotic
behavior for a given algorithm, then please explain to me how it differs
from the big-Omega and big-Theta notations. Wouldn't the big-O make
those obsolete?

Please read the wikipedia article on big O notation at
http://en.wikipedia.org/wiki/Big_O_notation

The fundamental error in your understanding is that you are
thinking about the big-o etc notation as statements about
algorithms; they are statements about functions. Here are some
of the functions associated with an algorithm:

The minimum time used for an input data set of size n.
The maximum time used for an input data set of size n.
The average time used for an input data set of size n, averaged
over all inputs.

The minimum space used for an input data set of size n.
The maximum space used for an input data set of size n.
The average space used for an input data set of size n, averaged
over all inputs.

These are all separate functions. We can make separate
statements about their asymptotic behaviours. Thus we can say
that the average time used by the quicksort algorithm is
O(n*log(n)) and the worst case is O(n^2).

The big-O notation says that the function inside O() is an
asymptotic bound; it isn't necessarily a best bound. In fact it
is quite proper to say that the average time for quicksort is
O(n^2), O(n^3), O(n^4), etc, as these are all valid upper bounds.

Big-O does not make big omega or big theta obsolete. Big omega
is any function asymptotically below the function of interest.
Big theta says (loosely) that big theta function has the same
asymptotic behaviour as the function it is being compared to.

Please, you are seriously misinformed, and are being very
dogmatic about your misunderstanding. Please read the wikipedia
article; I appreciate that it is a little dense, but it is clear
enough.
Richard Harter, cr*@tiac.net
http://home.tiac.net/~cri, http://www.varinoma.com
Save the Earth now!!
It's the only planet with chocolate.

[Richard Tobin]

In article <e9***************@read4.inet.fi>,
Juha Nieminen <no****@thanks.invalidwrote:

In computational complexity theory big-O is not a generic notation
used to describe some asymptotic behavior of an algorithm. It's used to
specify an upper bound to the asymptotic behavior of an algorithm.

I think you are conflating two different upper bounds here. If we say
the function f(n) is O(n) is we mean that there is a k such that
|f(n)| <= kn for sufficiently large n. That is, kn bounds f(n) over
the range of sufficiently large n.

When we apply this to sort algorithms, what is the function f? It
might be the worst-case time to sort a set of size n, or the average
time. So it's perfectly reasonable to say that quicksort is
O(n log(n)) on average and O(n^2) in the worst case, meaning that the
average time to sort a set of n elements is O(n log(n)) and the
worst-case time is O(n^2).

Or f might be the time to sort a set S, in which case we can say that
it is O(|S|^2), since now we are taking a bound over all the sets.
If we implicitly take n to be |S|, we can reasonably say that quicksort
is O(n^2).

-- Richard
--
Please remember to mention me / in tapes you leave behind.

[Antoninus Twink]

On 10 Nov 2008 at 21:11, Richard Harter wrote:

On Mon, 10 Nov 2008 18:36:00 GMT, Juha Nieminen <no****@thanks.invalidwrote:

> The big-O notation specifies the asymptotic upper bound for the
behavior of the algorithm. It does not specify anything else.

Please read the wikipedia article on big O notation at
http://en.wikipedia.org/wiki/Big_O_notation

The fundamental error in your understanding is that you are thinking
about the big-o etc notation as statements about algorithms; they are
statements about functions.

[snip]

Please, you are seriously misinformed, and are being very dogmatic
about your misunderstanding. Please read the wikipedia article

He is *so* misinformed and *so* dogmatic that he might decide that the
Wikipedia article is wrong and he's right, and vandalize the article.
It might be worth keeping an eye on it.

[Phil Carmody]

Juha Nieminen <no****@thanks.invalidwrites:

Even if you say "quicksort is O(n lg n) in average", the upper bound
is still not correct. Even when measuring average behavior quicksort
will behave slower than (n lg n) with some inputs, and thus the given
upper bound is incorrect.

There are no "some inputs" being forgotten about when such a
statement is being made. "On average" has included all inputs
(weighted by their probability).

Phil
--
I tried the Vista speech recognition by running the tutorial. I was
amazed, it was awesome, recognised every word I said. Then I said the
wrong word ... and it typed the right one. It was actually just
detecting a sound and printing the expected word! -- pbhj on /.

[CBFalconer]

Ben Bacarisse wrote:

>

.... big snip ...

>
But the time complexity for merge sort is also O(n^2). ...

Not so. It is O(nLOGn). Yes, you can disturb it into an O(n*n)
function, but that is abnormal. Mergesort is also stable and
requires no added memory.

--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home.att.net>
Try the download section.

[CBFalconer]

Jerry Coffin wrote:

cb********@yahoo.com says...

[ ... ]

>The result is that for most cases quicksort will be the fastest
sort. Right behind it are other O(nLOGn) methods. I prefer
mergesort and data input in lists, because then I don't have to
worry about the size to be sorted. In addition, mergesort is
stable (quicksort is not).

The most common implementation of Quicksort for arrays is unstable
-- but a Quicksort on an array _can_ be written to be stable if
you want to badly enough, and for a linked list, it's quite easy
to make it stable.

Not so. Extending Quicksort to include multiple fields does not
count. Mergesort remains simple. For an example, look at the
usage examples in hashlib (on my site).

--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home.att.net>
Try the download section.

[Juha Nieminen]

Phil Carmody wrote:

Juha Nieminen <no****@thanks.invalidwrites:

> Even if you say "quicksort is O(n lg n) in average", the upper bound
is still not correct. Even when measuring average behavior quicksort
will behave slower than (n lg n) with some inputs, and thus the given
upper bound is incorrect.

There are no "some inputs" being forgotten about when such a
statement is being made. "On average" has included all inputs
(weighted by their probability).

But in that case the given upper bound is incorrect.

Perhaps if you say "quicksort is amortized (n lg n)-time", that might
be closer to the truth.

[Phil Carmody]

Juha Nieminen <no****@thanks.invalidwrites:

Phil Carmody wrote:

>Juha Nieminen <no****@thanks.invalidwrites:

>> Even if you say "quicksort is O(n lg n) in average", the upper bound
is still not correct. Even when measuring average behavior quicksort
will behave slower than (n lg n) with some inputs, and thus the given
upper bound is incorrect.

There are no "some inputs" being forgotten about when such a
statement is being made. "On average" has included all inputs
(weighted by their probability).

But in that case the given upper bound is incorrect.

Bound of _what_? Define _precisely_ what function you are
talking about. It appears you've never heard the concept
of averaging. If so, you're going to be well out of depth
in this thread.

Phil
--
I tried the Vista speech recognition by running the tutorial. I was
amazed, it was awesome, recognised every word I said. Then I said the
wrong word ... and it typed the right one. It was actually just
detecting a sound and printing the expected word! -- pbhj on /.

[Juha Nieminen]

Antoninus Twink wrote:

He is *so* misinformed and *so* dogmatic that he might decide that the
Wikipedia article is wrong and he's right, and vandalize the article.
It might be worth keeping an eye on it.

Best troll post I have seen in a long time.

[Phil Carmody]

CBFalconer <cb********@yahoo.comwrites:

Ben Bacarisse wrote:

>>

... big snip ...

>>
But the time complexity for merge sort is also O(n^2). ...

Not so. It is O(nLOGn).

In that case it's O(n^2), and an infinitude of bigger things, too.

Phil
--
I tried the Vista speech recognition by running the tutorial. I was
amazed, it was awesome, recognised every word I said. Then I said the
wrong word ... and it typed the right one. It was actually just
detecting a sound and printing the expected word! -- pbhj on /.

[Antoninus Twink]

On 10 Nov 2008 at 22:08, CBFalconer wrote:

Ben Bacarisse wrote:

>But the time complexity for merge sort is also O(n^2). ...

Not so. It is O(nLOGn).

Once again, CBF shows that he doesn't have the first inkling of a clue
what he's talking about. Especially stupid since inclusions like
O(n log n) \subset O(n^2)
were the whole *point* of Ben's post...

[Phil Carmody]

Juha Nieminen <no****@thanks.invalidwrites:

However, what is "average" input in the case of quicksort?

ARGH! There is not an average input. That's crank speak.
I've seen your type on sci.math, and you'll be talking about
"infinite numbers" or the "probability of a number N being
prime". There is no average input, there's an average over
all inputs (with appropriate weightings, in this case
presumably uniform).

If you are lead to conclusions that seem to not make sense,
then it might just be that your premises and preconceptions
are all messed up.

Phil
--
I tried the Vista speech recognition by running the tutorial. I was
amazed, it was awesome, recognised every word I said. Then I said the
wrong word ... and it typed the right one. It was actually just
detecting a sound and printing the expected word! -- pbhj on /.

[Ben Bacarisse]

You may no read some of the replies you'd had so I will add my own...

CBFalconer <cb********@yahoo.comwrites:

Ben Bacarisse wrote:

>>

... big snip ...

>>
But the time complexity for merge sort is also O(n^2). ...

Not so. It is O(nLOGn).

<snip>

Every function that is O(n log n) is also O(n^2). That was my point.

--
Ben.

[Juha Nieminen]

Richard Harter wrote:

Big-O does not make big omega or big theta obsolete. Big omega
is any function asymptotically below the function of interest.

I fail to see how it does *not* make them obsolete.

Following your definition, "the worst case of insertion sort is
O(n^2)" and "the worst case of of insertion sort is Omega(n^2)" are
completely equivalent statements because both define bounds for the
"worst case of insertion sort" function.

Likewise "the best case of insertion sort is O(n)" and "the best case
of insertion sort is Omega(n)" are also completely equivalent.

Given that they specify upper and lower bounds, those are also
completely equivalent to the big-Theta notation.

In general, we can say "the behavior X for algorithm Y is O(f),
Omega(f) and Theta(f)".

[Antoninus Twink]

On 10 Nov 2008 at 23:07, Juha Nieminen wrote:

Richard Harter wrote:

>Big-O does not make big omega or big theta obsolete. Big omega
is any function asymptotically below the function of interest.

I fail to see how it does *not* make them obsolete.

That's because you don't understand what they mean, and you refuse to
accept your ignorance and find out.

Following your definition, "the worst case of insertion sort is
O(n^2)" and "the worst case of of insertion sort is Omega(n^2)" are
completely equivalent statements because both define bounds for the
"worst case of insertion sort" function.

This is nonsense. They are not equivalent statements, for much the same
reason that "x >= 7" and "x <= 12" are not equivalent statements,
even though they both define bounds for x.

[Kai-Uwe Bux]

Juha Nieminen wrote:

Richard Harter wrote:

>As others have pointed out, this is seriously misinformed. This
bit of folklore pops up every once in a while. Where does it
come from?

No, what is folklore is the custom of using the big-O notation to
describe *all* possible asymptotic behaviors of an algorithm. While that
may work colloquially, it's technically incorrect.

Do you have a reference for that? As far as I know, Big-O notation is rooted
in mathematics and can be used to describe the behavior of any function
(regardless where it comes from).

The big-O notation specifies the asymptotic upper bound for the
behavior of the algorithm. It does not specify anything else.

That is clearly false as Big-O notation is used in many places without
reference to any algorithm whatsoever. It is true that Big-O implies an
upper bound. However, that could be an upper bound, e.g., on best case
space complexity.

If the big-O notation could be used to describe *any* asymptotic
behavior for a given algorithm, then please explain to me how it differs
from the big-Omega and big-Theta notations. Wouldn't the big-O make
those obsolete?

No, the definitions of Big-O, Big-Omega, and Big-Theta differ considerably:

If f and g are functions from positive numbers to positive numbers, then

f = O(g) if f(x) < C g(x) for some C>0 and all sufficiently large x

f = Omega(g) if f(x) C g(x) for some C>0 and all sufficiently large x

f = Theta(g) if c g(x) < f(x) < C g(x) for some c>0 and C>0 and all
sufficiently large x.

However, Big-Theta can be defined in terms of the other two:

f=Theta(g) if and only if f=O(g) and f=Omega(g)

E.g.:

n^2 = O( n^2 )
n^2 = O( n^3 )
n^3 = Omega( n^2 )
n^2 = Theta( n^2 + n )
None of the above has any implications whatsoever about where the functions
involved come from. In particular, any of those can be used to talk about

worst case runtime
avergage case runtime
best case runtime
worst case space
average space
best case space
Best

Kai-Uwe Bux

[Juha Nieminen]

Antoninus Twink wrote:

Why should it exclude them? It AVERAGES OVER all inputs, good and bad
alike. The clue is in the word: AVERAGE.

Ok, let me see if I understood correctly. You basically define a
function like:

f1(n) = the average number of steps quicksort performs for all possible
inputs with n elements.

and f1(n) is O(n lg n).

Likewise you could define a function like:

f2(n) = the maximum number of steps quicksort performs for all possible
inputs with n elements.

and in this case f2(n) is O(n^2).

But in this case you can also say that f2(n) is Omega(n^2) and
Theta(n^2) because n^2 is a tight bound for f2.

What would be the function for which you can say "quicksort is
O(n^2) and Omega(n lg n)"?

[Juha Nieminen]

Antoninus Twink wrote:

> Following your definition, "the worst case of insertion sort is
O(n^2)" and "the worst case of of insertion sort is Omega(n^2)" are
completely equivalent statements because both define bounds for the
"worst case of insertion sort" function.

This is nonsense. They are not equivalent statements, for much the same
reason that "x >= 7" and "x <= 12" are not equivalent statements,
even though they both define bounds for x.

By "equivalent" I mean that both are defining the same bounding
function (n^2) and both are valid. My real point was why have an O
notation and an Omega notation, when the Theta notation is telling what
we want? The O and Omega notations seem obsolete.

[CBFalconer]

Ben Bacarisse wrote:

CBFalconer <cb********@yahoo.comwrites:

>Ben Bacarisse wrote:

... big snip ...

>>>
But the time complexity for merge sort is also O(n^2). ...

Not so. It is O(nLOGn).

<snip>

Every function that is O(n log n) is also O(n^2). That was my
point.

You are very wrong. In C, n^2 is n XOR 2, and O(n^2) is quite
fast. But, if we use reasonable notation and ask about O(n*n) we
find that to be much slower than O(n log n).

--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home.att.net>
Try the download section.

[Ben Bacarisse]

CBFalconer <cb********@yahoo.comwrites:

Ben Bacarisse wrote:

>CBFalconer <cb********@yahoo.comwrites:

>>Ben Bacarisse wrote:

... big snip ...

But the time complexity for merge sort is also O(n^2). ...

Not so. It is O(nLOGn).

<snip>

Every function that is O(n log n) is also O(n^2). That was my
point.

You are very wrong. In C, n^2 is n XOR 2, and O(n^2) is quite
fast. But, if we use reasonable notation and ask about O(n*n) we
find that to be much slower than O(n log n).

Are you just repeating your now rather tired joke? If so, fine, I'll
leave it, but if not, do you really dispute that the time complexity
of merge sort (typically measured as the comparisons made) is also
O(n*n)?

--
Ben.

[Ben Bacarisse]

Juha Nieminen <no****@thanks.invalidwrites:

Antoninus Twink wrote:

>Why should it exclude them? It AVERAGES OVER all inputs, good and bad
alike. The clue is in the word: AVERAGE.

Ok, let me see if I understood correctly. You basically define a
function like:

f1(n) = the average number of steps quicksort performs for all possible
inputs with n elements.

and f1(n) is O(n lg n).

Yes, though since this is getting messy I should own up and say that I
have no reference for that. In Knuth TAOCP, the derivation ends with
an approximation. I think I once saw a full combinatorial analysis of
your f1 and the result was more complex that O(n lg n) but I may be
miss-remembering.

Likewise you could define a function like:

f2(n) = the maximum number of steps quicksort performs for all possible
inputs with n elements.

and in this case f2(n) is O(n^2).

But in this case you can also say that f2(n) is Omega(n^2) and
Theta(n^2) because n^2 is a tight bound for f2.

What would be the function for which you can say "quicksort is
O(n^2) and Omega(n lg n)"?

Both f1 and f2. You are correct that f2 is Omega(n^2) (which gives us
Theta, too) but any function that is Omega(n^2) is also Omega(n lg n)
and Omega(n) and Omega(log n) and...

--
Ben.

[Ben Bacarisse]

Juha Nieminen <no****@thanks.invalidwrites:

Antoninus Twink wrote:

>> Following your definition, "the worst case of insertion sort is
O(n^2)" and "the worst case of of insertion sort is Omega(n^2)" are
completely equivalent statements because both define bounds for the
"worst case of insertion sort" function.

This is nonsense. They are not equivalent statements, for much the same
reason that "x >= 7" and "x <= 12" are not equivalent statements,
even though they both define bounds for x.

By "equivalent" I mean that both are defining the same bounding
function (n^2) and both are valid.

I am sure you agree that using "equivalent" like that is going to lead
to trouble! Defining an upper bound and a lower bound are very
different even if the bound is the same. (AT's example is a bad one.
x >= 7 and x <= 7 would have been better. They are still not
equivalent statements despite the identical bound.)

My real point was why have an O
notation and an Omega notation, when the Theta notation is telling what
we want? The O and Omega notations seem obsolete.

You are right. If we could always get tight bounds like Theta(f) then
why bother with anything else. The trouble is that this is often very
hard indeed -- especially in the "average" case that started all this.
You don't see many published big-Omega results because people rarely
care (knowing that algorithm X is never takes more than that n^4 steps
is not helpful if it is really much worse than that) but getting a
slightly better upper bound is step forward (i.e. proving that
algorithm X takes no more than n^4.24 steps).

--
Ben.

[Jerry Coffin]

In article <49***********************@read.cnntp.org>,
jk********@gmx.net says...

[ ... ]

Leaving out the scanning forward and backward part (swapping offending
pairs), you are missing the most important point about quicksort, namely
the one that explains the speed. In terms of number of comparisons,
quicksort is not doing better than, say, heapsort. However, when it comes
to moving elements around in memory, quicksort has a huge advantage.
Experimentally, the number of moves is one place quicksort beats the other
algorithms whereas the number of comparisons is not. Declaring the very
feature of quicksort that makes this happen to be a minor issue seems
weird.

Of course, that only applies to sorting sequences. For linked structures,
the number of pointer operations would be relevant.

I'll tell you what: if you're really convinced that scanning forward and
backward, and swapping elements in the list will reduce the number of
pointer operations, why don't you implement both and find out?

I've done so: swapping loses -- badly. Splicing an item to a list
requires only one pointer operation. Doing the forward and backward
scanning means you need a doubly linked list. Swapping one pointer takes
the usual three operations, and a doubly linked list obviously has two
pointers per node, so a swap instead of a splice takes six operations
instead of one.

--
Later,
Jerry.

The universe is a figment of its own imagination.

[Paul Hsieh]

On Nov 10, 10:38*am, Juha Nieminen <[e-mail]:

James Kanze wrote:

On Nov 8, 12:27 am, user923005 <[e-mail]:

On Nov 7, 2:47 pm, Juha Nieminen <[e-mail]:
Sure. *If hash(x) == return 1; then bad behavior is to be
expected. *The assumption is of maximally cascade free hash
functions like UMAC or Bob Jenkin's hash.

Do you have any references on those, particularly with an
implementation? *All I found for UMAC was a reference to book,
and Bob Jenkin's seems more concerned with cryptographic hashing
than anything else. *If these are standard and widely used
algorithms for look-up hashing, I'd like to add them to my set
of hashing benchmarks.

(Note that cryptographic hashing and look-up hashing have very
different constraints, and a good hash function for one isn't
necessarily a good hash function for the other. *Also, in
look-up hashing, speed counts. *Taking 10 times more time to get
1% better distribution on the average is a loss.)

The arena of "practical non-cryptographic hash functions" is clearly a
relatively new field. Outside of crypto-hashes, Bob Jenkin's function
and my function, the quality of everything else out there is truly
pathetic.

Bob Jenkins, for a long time, set the standard with his lookup2
function (I think he wrote and publicized it in Dr. Dobb's journal in
1996 or so.) However, in a kind of "first attempt" I was able to
design a hash function myself that was dramatically faster and had
similar quality. (My function passes Bob Jenkins' avalanche test as
well as my own far more stringent bit distribution and correlation
test; Bob's function performs slightly worse on my test.) So its
clear that there is plenty of room for research here if anyone cares
to take the time or put in the effort. Bob rewrote a version of his
function, which apparently comes much closer to the performance of my
function, but I have not gone back to check it.

Bob and I took different approaches. He started with something
cryptographic, and knocked it down to a point where it was faster,
though losing the cryptographic properties that were no longer
required. I instead took some ideas of his, and built a function from
the ground up that has no pedigree from any cryptographic function.
My design took modern CPU architecture into account as well as trying
to get to "the heart of the matter" for hash function quality
requirements. So I started with a framework which I knew would
deliver a high performance result and injected quality into it.

The key point behind both our functions is that they are not only good
quality, they are objectively faster than all the other typically used
hash functions (CRC, Dan Bernstein's ASCII hash, FNV hash, etc). The
only things that even compete with our functions are things people
already know are worthless (like just summing up the bytes.)

This situation has lead to *some* efforts from other people. In
particular the author of the "murmur hash" (or whatever its called) is
a major proponent of his own function which is even faster than my
function, however it also has clear weaknesses and seems quite
affixedly tied to the x86 architecture. Others have used genetic
algorithms to come up with weird stuff in x86 assembly language which
is very hard to analyze.

In short, hunting around in "the literature" is not going to lead to
too much insightful information. Aside from Bob and myself, there has
been very little serious work in high performance hash functions.
That said, both his function and mine are very usable in real world
practical environments.

* I'm pretty sure Jenkin's hashing function (which uses the same
algorithm as his ISAAC random number generator) is faster than anything
you could ever create yourself, having even a fraction of the same quality.

Is that a commentary on what you think of James Kanze's abilities, or
are you just indirectly praising people like Bob Jenkins and myself as
being some kind of untouchable uber-programmers? If the latter, I
would say its likely unwarranted. This problem is wide open for
anyone with good math/programming skills with a good rough idea about
modern CPU performance. Specifically: the mantle is up for grabs for
anyone to come up with a good *64 bit* hash function. Ironically, my
gut feeling is that it should be possible to come up with a function
nearly twice as fast as mine if you can make the assumption that your
platform natively supports 64 bit scalars (which modern systems now
do.) So its not like Bob and I have set some unattainable bar for
performance. (The only thing that prevents *ME* from setting that
high bar again these days is that I have a day job.)

--
Paul Hsieh
http://www.pobox.com/~qed/hash.html
http://bstring.sf.net/

[Keith Thompson]

CBFalconer <cb********@yahoo.comwrites:

Ben Bacarisse wrote:

[...]

>Every function that is O(n log n) is also O(n^2). That was my
point.

You are very wrong. In C, n^2 is n XOR 2, and O(n^2) is quite
fast. But, if we use reasonable notation and ask about O(n*n) we
find that to be much slower than O(n log n).

Why are you complaining about "^" to denote exponentiation, but not
complaining about "n log n" to mean "n * log(n)"? Both "n log n" and
"n^2" are obviously intended to be mathematical notation (with "^"
implying a superscript, i.e., exponentation), not C expressions.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

[Antoninus Twink]

On 11 Nov 2008 at 2:24, Ben Bacarisse wrote:

Juha Nieminen <no****@thanks.invalidwrites:

> Ok, let me see if I understood correctly. You basically define a
function like:

f1(n) = the average number of steps quicksort performs for all possible
inputs with n elements.

and f1(n) is O(n lg n).

Yes, though since this is getting messy I should own up and say that I
have no reference for that. In Knuth TAOCP, the derivation ends with
an approximation.

But this approximation just replaces evaluations of the harmonic
function by the leading term in its asymptotic expansion, established
way back in 1.2.7(3), so concluding from this approximation that the
average runtime is O(n log n) is completely rigorous.

[Antoninus Twink]

On 11 Nov 2008 at 2:34, Ben Bacarisse wrote:

Juha Nieminen <no****@thanks.invalidwrites:

>My real point was why have an O notation and an Omega notation, when
the Theta notation is telling what we want? The O and Omega notations
seem obsolete.

You are right. If we could always get tight bounds like Theta(f) then
why bother with anything else. The trouble is that this is often very
hard indeed -- especially in the "average" case that started all this.

Well, there are two things. As you say, we might not always be able to
get a lower bound because the theory is too hard, so we write big-O for
the best-known upper bound. A good example is matrix multiplication,
where the best upper bound is currently about O(n^2.4), but AFAIK there
isn't even any Omega(n^(2+epsilon)) lower bound known.

But often, even when we do have a Theta result, people still use the O
notation. Why? Maybe just because O is a Roman character that's easy to
type? Maybe because when we're programming in the real world, all we
care about is some rough indication of how well our algorithm is likely
to scale, and not the mathematical minutiae? Or it's just convention? Or
laziness?

[James Kanze]

On Nov 10, 3:48*am, Kai-Uwe Bux <[e-mail]:

Jerry Coffin wrote:

In article <[e-mail]>, [e-mail] says...

[ ... ]

The result is that for most cases quicksort will be the
fastest sort. *Right behind it are other O(nLOGn) methods.
*I prefer mergesort and data input in lists, because then I
don't have to worry about the size to be sorted. *In
addition, mergesort is stable (quicksort is not).

The most common implementation of Quicksort for arrays is
unstable -- but a Quicksort on an array _can_ be written to
be stable if you want to badly enough, and for a linked
list, it's quite easy to make it stable.

My linguistic intuitions differ: Quicksort _is_ the algorithm
published as Algorithm 64 (and 63) by C.A.R. Hoare in the
Communications of the ACM. That algorithm sorts a sequence in
place and is not stable. It makes 2n*log(n) comparisons on
average and (1/3)n*log(n) exchanges on average. Anything that
is stable or deals with linked lists is an implementation of a
_different_ algorithm (and probably has different average
complexities).

The algorithm presented by Hoare in Algorithm 64 is very
general; it only refers to algorithm 63, and presumably,
anything that achieves a partition with similar properties would
be acceptable.

I am not saying that there are no refinements or other
algorithms based on similar ideas. Some of these algorithms
are stable and some apply to linked lists. Also, I am not a
native speaker of English. Nonetheless, I feel that algorithms
have a certain identity (which makes it meaningfull to say
that a certain sorting algorithm is stable); and that
implementations of an algorithm must preserve that identity
and the associated characteristics to count as implementations
_of_ that algorithm.

So you're saying that the implementation proposed by Jon Bentley
(section 10.2 of _Programming_ _Pearls_, which is just a reprint
of one of his columns in the CACM) isn't a quick sort, although
he claims it to be one. (I think his algorithm is actually
stable, although I haven't verified; it may have problems if
there are objects equal to the pivot. But I think it could
easily be fixed.)

My understanding is that the term quick sort is applied to all
algorithms that partition, then sort each partition recursively.

(Also, of course, it's trivial to implement quick sort for a
list; just implement [] in terms of std::advance. Of course,
the adjective "quick" might not be so appropriate then, but the
algorithm stands.)

--
James Kanze (GABI Software) email:ja*********@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, [phone]

[James Kanze]

On Nov 10, 8:43*pm, Juha Nieminen <[e-mail]:

Andre Kostur wrote:

Not necessarily true. *The big-O could refer to best-case,
average, worst- case, or anything in between. *You just need
to specify it. *As I recall, quicksort is O(n lg n) in the
average case, O(n^2) worst case. *Both say something
interesting about the algorithm.

While you can say that colloquially, it's formally quite
shaky.

Yes and no.

In computational complexity theory big-O is not a generic
notation used to describe some asymptotic behavior of an
algorithm. It's used to specify an upper bound to the
asymptotic behavior of an algorithm.

More or less. It's usually defined in terms of numbers of some
specific operation, or numbers of some specific object, rather
than in terms of runtime or memory. And of course, who ever is
using the term must define the conditions involved. It does
make sense to speak of a "typical big-O", i.e. a value which
holds "most of the time", even if there isn't a very rigorous
definition for "typically".

Saying, for example, "insertion sort is O(2^n)" is completely
valid. O(n^100) is equally valid. The big-O notation does not
even require for the upper bound to be tight. Any upper bound
is valid as long as the algorithm never behaves slower than
that. However, saying "insertion sort is O(n)" is not valid
because with some inputs insertion sort performs
asymptotically more steps than that.

Even if you say "quicksort is O(n lg n) in average", the upper
bound is still not correct. Even when measuring average
behavior quicksort will behave slower than (n lg n) with some
inputs, and thus the given upper bound is incorrect.

I don't think anyone has ever claimed that "quicksort is O(n lg
n) in average", or typically. The claim is that it is
"typically close to O(n lg n)". And yes, I know: throw in
enough weasel words, and anything is true. In this case,
however, there is some useful (albeit not very precise)
information being communicated: if you use quick sort, it's
highly unlikely that your performance will be significantly
worse than O(n lg n). (More weasel words:-): "highly unlikely"
and "significantly worse".) The fact remains that I've done a
fair amount of benchmarking of sorting routines, and unless I
did it intentionally (e.g. use the first element for a pivot
with an already sorted array), quick sort was always the
fastest, and the actual plotted curve was pretty close to O(n lg
n).

Likewise the big-Omega notation is used to set a lower bound
to the asymptotic behavior of an algorithm. For example if you
say "insertion sort is Omega(n)", you are telling that
insertion sort never performs less steps than an amount
linearly relative to the size of the input.

Saying "the best case for insertion sort is O(n)" is exactly
as silly as saying "the worst case for insertion sort is
Omega(n^2)". They don't make sense as bounds in these
sentences. They are misused to describe some special cases.

You have to be careful when discussing vocabulary. Different
people use the same words differently. And in the end, there's
no real right or wrong.

--
James Kanze (GABI Software) email:ja*********@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, [phone]

[James Kanze]

On Nov 10, 8:52*pm, Pete Becker <[e-mail]:

On 2008-11-10 14:43:06 -0500, Juha Nieminen <[e-mail]:

Even if you say "quicksort is O(n lg n) in average", the
upper bound is still not correct. Even when measuring
average behavior quicksort will behave slower than (n lg n)
with some inputs, and thus the given upper bound is
incorrect.

You can't ignore the qualifier "on average", which implies
some constraints on input sequences.

That's not my understanding of "on average". My understanding
is that given enough different input sequences, the "average" of
all of the times will be O(n lg n). But as far as I know, that
isn't the case for quicksort. It's been a long time since I
studied this, so there may be some advances, but as I recall,
the mathematical analysis of the average behavior of quicksort
was too complex to be done. All that one could say is that the
results of many trials seemed to indicate that the average
performance wasn't too much greater than O(n lg n), despite a
few outlying values.

Yes, it's O(n^2) for some input sequences, but if you rule out
those input sequences, then it's O(nlogn), and that's all that
"on average" means.

No. For it to hold "on average", you have to consider those
input sequences as well. On average, in this case, means that
they will occur rare enough that they won't have a measurable
effect on the average. (If you do a million different trials,
and one takes 1000 seconds, and all of the others take 10
seconds, what is the average?

Big-oh notation tells you what happens when the input sequence
gets long. It doesn't tell you anything about the contents of
input sequences.

No, but you have to define what you are measuring. Whether you
are measuring worst-case behavior, best-case behavior, average
behavior, or median behavior? Or something else completely,
like memory use. (And of course, you also have to define the
units you're measuring in---seconds, comparisons, comparisons
and swaps...)

--
James Kanze (GABI Software) email:ja*********@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, [phone]

[James Kanze]

On Nov 11, 11:54*am, Pete Becker <[e-mail]:

It's well understood what sort of input causes O(n^2) behavior.

Really? If I post a quicksort implementation here, could you
give me an algorithm which would generate the worst case?
(I guess there should a smiley here, because I don't think that
that's really what you meant. But just a half of one, because
I'd really like to find such. There are times where you do want
to test worst case.)

--
James Kanze (GABI Software) email:ja*********@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, [phone]

[James Kanze]

On Nov 10, 7:36*pm, Juha Nieminen <[e-mail]:

Richard Harter wrote:

As others have pointed out, this is seriously misinformed.
*This bit of folklore pops up every once in a while. *Where
does it come from?

No, what is folklore is the custom of using the big-O notation
to describe *all* possible asymptotic behaviors of an
algorithm. While that may work colloquially, it's technically
incorrect.

The big-O notation specifies the asymptotic upper bound for
the behavior of the algorithm. It does not specify anything
else.

Big-O predates computer algorithms by at least 50 years. Big-O
defines an asymptotic upper bound for a function. That function
can be the number of comparisons in the worst case execution of
quick sort, for a given array size, or it can be the average
number of comparisons, for a given array size, or it can be the
best case, for a given array size. Or it can include data
moves, or it can measure memory use in some unit. What is true
is that it has nothing to do with "algorithms", per se; it can
only be applied to algorithms when you define a function which
involves an algorithm.

--
James Kanze (GABI Software) email:ja*********@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, [phone]

[James Kanze]

On Nov 10, 7:38*pm, Juha Nieminen <[e-mail]:

James Kanze wrote:

On Nov 8, 12:27 am, user923005 <[e-mail]:

On Nov 7, 2:47 pm, Juha Nieminen <[e-mail]>
wrote: Sure. *If hash(x) == return 1; then bad behavior is
to be expected. *The assumption is of maximally cascade
free hash functions like UMAC or Bob Jenkin's hash.

Do you have any references on those, particularly with an
implementation? *All I found for UMAC was a reference to
book, and Bob Jenkin's seems more concerned with
cryptographic hashing than anything else. *If these are
standard and widely used algorithms for look-up hashing, I'd
like to add them to my set of hashing benchmarks.

(Note that cryptographic hashing and look-up hashing have
very different constraints, and a good hash function for one
isn't necessarily a good hash function for the other. *Also,
in look-up hashing, speed counts. *Taking 10 times more time
to get 1% better distribution on the average is a loss.)

I'm pretty sure Jenkin's hashing function (which uses the same
algorithm as his ISAAC random number generator) is faster than
anything you could ever create yourself, having even a
fraction of the same quality.

We can easily find out. If someone will post a link to the
algorithm, I'll implement it and measure. I've already got the
harness. (The hash table being used is a template, so all I
need to do is implement a traits class with isEqual and hashCode
functions for std::string. Or just have it derive from
StrIsEqual, which provides the isEqual function. Or just point
me to the algorithm, and I'll translate it myself.)

FWIW: I've got a JenkinsHash already, from
http://burtleburtle.net/bob/hash/doobs.html. It is considerably
worse than any of my own hashing functions or FNV hashing, for
all measured inputs. If this is the one you're talking about,
don't bother. For look-up hashing, it's not particularly good.
(It may be cryptographicly secure, which mine aren't. That's
something I don't know about.)

--
James Kanze (GABI Software) email:ja*********@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, [phone]

[Kenny McCormack]

In article <ln************@nuthaus.mib.org>,
Keith Thompson <ks***@mib.orgwrote:

>CBFalconer <cb********@yahoo.comwrites:

>Ben Bacarisse wrote:

[...]

>>Every function that is O(n log n) is also O(n^2). That was my
point.

You are very wrong. In C, n^2 is n XOR 2, and O(n^2) is quite
fast. But, if we use reasonable notation and ask about O(n*n) we
find that to be much slower than O(n log n).

Why are you complaining about "^" to denote exponentiation, but not
complaining about "n log n" to mean "n * log(n)"? Both "n log n" and
"n^2" are obviously intended to be mathematical notation (with "^"
implying a superscript, i.e., exponentation), not C expressions.

Because CBF still thinks he is a regular - and thus entitled to the
benefits that accrue therefrom - i.e., being allowed to be a mindless
nitpicker.

[Richard Harter]

On Tue, 11 Nov 2008 06:15:20 -0800 (PST), James Kanze
<ja*********@gmail.comwrote:

>On Nov 11, 11:54=A0am, Pete Becker <[e-mail]:

>It's well understood what sort of input causes O(n^2) behavior.

Really? If I post a quicksort implementation here, could you
give me an algorithm which would generate the worst case?
(I guess there should a smiley here, because I don't think that
that's really what you meant. But just a half of one, because
I'd really like to find such. There are times where you do want
to test worst case.)

There is a published procedure that is very general that is one
the web somewhere that I can't find at the moment. The essence,
though, is that you use an oracle. It works like this: At each
step you tell me how you're going to pick your pivot, i.e., what
O(1) elements you are going to look at to choose the pivot. I
get to choose the values of the all of the rest. I choose them
so that they are all bigger (smaller) than your pivot. I don't
actually have to set their values until you look at them; I just
have to place bounds on them.
Richard Harter, cr*@tiac.net
http://home.tiac.net/~cri, http://www.varinoma.com
Save the Earth now!!
It's the only planet with chocolate.

[Juha Nieminen]

James Kanze wrote:

>Even if you say "quicksort is O(n lg n) in average", the upper
bound is still not correct. Even when measuring average
behavior quicksort will behave slower than (n lg n) with some
inputs, and thus the given upper bound is incorrect.

I don't think anyone has ever claimed that "quicksort is O(n lg
n) in average", or typically. The claim is that it is
"typically close to O(n lg n)". And yes, I know: throw in
enough weasel words, and anything is true. In this case,
however, there is some useful (albeit not very precise)
information being communicated: if you use quick sort, it's
highly unlikely that your performance will be significantly
worse than O(n lg n). (More weasel words:-): "highly unlikely"
and "significantly worse".) The fact remains that I've done a
fair amount of benchmarking of sorting routines, and unless I
did it intentionally (e.g. use the first element for a pivot
with an already sorted array), quick sort was always the
fastest, and the actual plotted curve was pretty close to O(n lg
n).

I think that what I really misunderstood with "is O(n lg n) in
average" is what is (mathematically) meant with "average" in this
particular context.

I have understood "upper bound" to mean that the behavior *never*
exceeds that bound. In other words, if g(n) is the upper bound of f(n),
then f(n) is *never* larger than k*g(n), for a sufficiently large k (at
least from a given n forward). From this I understand that if f(n) ever
gets larger than k*g(n), then g(n) is not the true upper bound for f(n).
Even if f(n) does not exceed k*g(n) "in average", if it exceeds it even
once, then g(n) is simply not the correct upper bound.

However, apparently the "in average" in this particular context means
something slightly different. More precisely, the function f(n) is
defined as:

f(n) = the average amount of steps the algorithm performs for an input
of size n (with all possible different inputs of that size)

In this case the f(n) function can indeed have a smaller upper bound
than the worst case for the algorithm in question.

I think the "in average" is a bit confusing.

[Juha Nieminen]

Paul Hsieh wrote:

> I'm pretty sure Jenkin's hashing function (which uses the same
algorithm as his ISAAC random number generator) is faster than anything
you could ever create yourself, having even a fraction of the same quality.

Is that a commentary on what you think of James Kanze's abilities, or
are you just indirectly praising people like Bob Jenkins and myself as
being some kind of untouchable uber-programmers?

It wasn't my intention to belittle Kanze's abilities. I used that
expression as a kind of colloquialism. I admit that it can easily be
understood as belittling. I apologize for that.

What I objected to was Kanze's suggestion that a cryptographically
strong hashing function may often be significantly slower than a
good-enough hashing function for a generic hash table. In my experience
Jenkin's algorithm is both cryptographically strong and very very fast
at the same time (much faster than eg. simple linear congruential
generators, which are usually cryptographically extremely weak).

If the latter, I would say its likely unwarranted.

If you say so. But I still admire Jenkin's rng. It's extremely fast
and the randomness is of superb quality.

[Juha Nieminen]

James Kanze wrote:

>I'm pretty sure Jenkin's hashing function (which uses the same
algorithm as his ISAAC random number generator) is faster than
anything you could ever create yourself, having even a
fraction of the same quality.

We can easily find out.

As I commented in the other post, I didn't mean that to be belittling
or as a challenge, but as a colloquial expression. I see now how it can
be understood in the wrong way. Thus I apologize for my poor choice of
words.