> I will open this can and say that average case complexity is the most > important. For example sorting O(nlogn) and dict lookup O(1).
I would still debate the complexity of dict lookup. What are you averaging over? In absence of any distribution property of hash functions in the average case, you can't say anything about dictionary performance. I also disagree that the average complexity is "most important". I find the worst-case complexity most important. For average-case complexity, I just measure my application, and don't care about theoretical numbers. > Notes are nice and already exist at random places in the *huge* > documentation archive. But I still believe that the best place for this > are the already existing tables in the docs (I pointed them at my > initial post). One should trivially be able to find this information. Feel free to start a Wiki page then. With the right keywords on the page, it shouldn't take long for Google to pick up the page, and return it to people asking the right questions. > I agree that CPython docs should document CPython behaviour. Actually, no. The "CPython documentation" documents Python, the language, and its standard library. It is a specification that CPython conforms to (hopefully). There might be fragments in it that are both worthwhile-to-mention and implementation-specific, but they should be marked as the latter. > Hmmm, the first thing that comes to mind is prepending an item in a list > which is small and seems nice, but is O(n) I think! And besides that, > for someone who *cares* about his code good looks is not enough... Define "small". For a theoretically-reasonable definition of "small", prepending is O(1): namely, when a "small" list is one whose size is bounded by some upper bound (say, M). For such a list, prepending is O(1) (namely, not more than M copies). Of course, you can only prepend a finite number of times to such a list, unless you also delete in-between. Over a long series of insertions and deletions, prepending will be O(1) (if M is large, with a large factor). Regards, Martin _______________________________________________ Python-Dev mailing list Python-Dev@python.org http://mail.python.org/mailman/listinfo/python-dev Unsubscribe: http://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
