Performance: sets vs dicts.

[John Bokma]

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/