hash and __eq__

[Steven D'Aprano]

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