[Python-Dev] Complexity documentation request

[Greg Ewing]

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