hash and __eq__

[Arnaud Delobelle]

Steven D'Aprano <steve at REMOVE-THIS-cybersource.com.au> writes:

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

OK.  I remember from my student years when studying complexity theory
that complexity implicitely referred to worst case complexity.  I
assumed this was a widely used convention - I don't have any evidence
that it is so you may very well be correct.

Anyway, it's good to know that quicksort is O(n^2) in the worst case -
and that this worst case can crop up very easily in some situations,
especially if not too much care has been taken implementing it.

[...]

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

But the OP only mentioned 'complexity', not 'average complexity', and I
imagine that he knows the average case complexity of accessing a key in
a hashtable.

-- 
Arnaud