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 -- http://mail.python.org/mailman/listinfo/python-list
