Re: hash and __eq__

On Sun, 31 May 2009 07:24:09 +0100, Arnaud Delobelle wrote:

AFAIK, 'complexity' means 'worst case complexity' unless otherwise
stated.

No, it means "average or typical case" unless otherwise specified.
Consult almost any comp sci text book and you'll see hash tables with
chaining (like Python dicts) described as O(1) rather than O(N),
Quicksort as O(N log N) instead of O(N**2), and similar. If the default
was "worst case unless otherwise specified", then Quicksort would be
called "Slower than Bubblesort Sort".

(Both are O(N**2), but Quicksort does more work.)

Here's a quote on-line:

"You should be clear about which cases big-oh notation describes. By
default it usually refers to the average case, using random data.
However, the characteristics for best, worst, and average cases can be
very different..."

http://leepoint.net/notes-java/algorithms/big-oh/bigoh.html


It is simply misleading to describe dicts as O(N) without the
qualification "if the data is chosen maliciously, or otherwise by an
incredible fluke". And even if it isn't, Piet explicitly said he was
talking about the average behaviour, not worst.



--
Steven
.

Relevant Pages