On 9/3/10 12:08 PM, John Bokma wrote:
Terry Reedy<tjre...@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
--
http://mail.python.org/mailman/listinfo/python-list
