Performance: sets vs dicts.

[Robert Kern]

On 9/3/10 12:08 PM, John Bokma wrote:
> 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.

That's an ambiguous wording that is likely to confuse people. It seems like you 
are saying that the O() behavior is the order of the first derivative of the 
running time as a function of some interesting parameter of the problem, which 
it is not. O() notation *describes* the growth, but it *is not* the order of the 
growth itself.

-- 
Robert Kern

"I have come to believe that the whole world is an enigma, a harmless enigma
  that is made terrible by our own mad attempt to interpret it as though it had
  an underlying truth."
   -- Umberto Eco