hash and __eq__

[Scott David Daniels]

Arnaud Delobelle wrote:
> 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. 

I think you both are standing on opposite sides of a shift in notation.
Mathematics changes notations all the time, and new students are
presented notation as if it were a fixed thing.  What I think is
happening is that O-notation was a very technical notation used
for comparing abstract algorithms (providing an analysis that would
survive centuries of engineering improvement of the machines).  More
recently we have seen more use of average-case performance analysis,
in service of shorter-term accuracy (I guess).  Certainly this has
given us some data structures that would be hard to justify on a
worst-case analysis.  I suspect the default is shifting towards
average case (although it may already be there).  Certainly best
practice for the next couple of decades would be to be explicit
about the meaning

--Scott David Daniels
Scott.Daniels at Acm.Org