Martin v. Löwis wrote: > I would still debate the complexity of dict lookup. What are you > averaging over?
All the Python programs I've ever run. :-) > I also disagree that the average complexity is "most important". > I find the worst-case complexity most important. While in theory the worst-case behaviour of a hash table is O(n), in practice the worst case is so vanishingly rare that nobody worries about it. Can you really say that you don't make any design decisions early on based on the assumption that dict lookup will almost certainly be a lot faster than searching a list? >>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! > > Define "small". I think he was talking about the size of the code. In other words, just because the code is small doesn't necessarily mean the algorithm is efficient. > For a theoretically-reasonable definition of "small", > prepending is O(1): Big O-notation is all about the limit when things get big. So it doesn't make sense to talk about "O() when something is small". -- Greg _______________________________________________ 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
