Performance: sets vs dicts.
john at castleamber.com
Fri Sep 3 19:08:02 CEST 2010
Terry Reedy <tjreedy at udel.edu> writes:
> On 9/1/2010 8:11 PM, John Bokma wrote:
> Right. And if 'small values of n' include all possible values, then
> rejecting a particular O(log n) algorithm as 'unacceptable' relative
> to all O(1) algorithms is pretty absurd.
I have little time, but want to reply to this one: anyone using big-Oh
and claiming that an O(log n) algorithm is 'unacceptable' relative to
all O(1) algorithms has no clue what he/she is talking about.
big-Oh says something about the order of /growth/ of the running time of
an algorithm. And since 1 is a constant O(1) means that the order of
/growth/ of the running time is constant (independend of the input
size. Since "the growth of the running time is constant" is quite a
mouth full, it's often shortened to 'constant time' since from the
context it's clear what's being meant. But this doesn't mean
that if the algorithm gets an input size of 100000 versus 1 that it
takes the same number of seconds for the latter to process.
John Bokma j3b
Blog: http://johnbokma.com/ Facebook: http://www.facebook.com/j.j.j.bokma
Freelance Perl & Python Development: http://castleamber.com/
More information about the Python-list