Steven D'Aprano <st...@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 -- http://mail.python.org/mailman/listinfo/python-list
