sorting a dictionary

[Christopher A. Craig]

Paul Rubin <phr-n2003b at NOSPAMnightsong.com> writes:

> "Giovanni Bajo" <noway at sorry.com> writes:
> > Doesn't d[k] require O(logN) too? Or is Python smart enough to
> > optimize this away since we are going through the dictionary?
> 
> Dictionary access is supposed to be constant time (hash lookup).

Dictionary access is constant time on average, but big O doesn't
denote average.  Dictionary lookup is O(N), and those lookups are not
optimized out.

-- 
Christopher A. Craig <list-python at ccraig.org>
"The problem with X is that it's overadequate" Dennis Ritchie