Benchmarks

[CBFalconer]

Nick Keighley said:



If you do, fist get it spell-checked.

^^^^
?? F'ups set.

 

[Phil Carmody]

^^^^
?? F'ups set.

Set, followed, and had fun with.



extern volatile poster Chuck;

void Richard(post fromNick)
{
string s("W");
while(!Chuck.posted()) { s+="o"; }
s+="sh";
Chuck.respond(s);
}

Phil

 

[James Kanze]

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

 

[CBFalconer]

.... snip ...


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?

Because, for example, if you pick an extreme position as the mark
for each phase, and the input array is either sorted or inversely
sorted, you will trigger that O(n*n) operation. With slight care
this becomes very rare. For any input array and any algorithm it
is possible to find an order that will trigger that worst case.
But they are rare.

 

[Jerry Coffin]

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.

 

[Kai-Uwe Bux]

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]

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]

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]

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]

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]

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]

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]

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.

 

[Ben Bacarisse]

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.

 

[Tim Rentsch]

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]

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 Tobin]

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

 

[Antoninus Twink]

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]

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

 

[CBFalconer]

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