Performance: sets vs dicts.

[Terry Reedy]

On 9/1/2010 8:11 PM, John Bokma wrote:
> Terry Reedy<tjreedy at udel.edu>  writes:
>
>> On 9/1/2010 5:40 PM, John Bokma wrote:
>
> [..]
>
>> Yes, I switched, because 'constant time' is a comprehensible claim
>> that can be refuted and because that is how some will interpret O(1)
>> (see below for proof;-).
>
> You make it now sound as if this interpretation is not correct or out of
> place.

Saying that an interpretation is comprehensible and common is hardly a 
putdown ;-). It simply is not unique. I also said that the other 
interpretation is not coherent for size-limited problems. However, if 
you mean 'constant', whatever you mean by that, why not say so?

Here is the technical definition given in
https://secure.wikimedia.org/wikipedia/en/wiki/Big_O_notation
I assure you that it is the standard one invented by a mathematiciam 
over a century ago and used by mathematicians ever since. It was 
popularized in computer science by Donald Knuth in 1976 and used in The 
Art of Computer Programming. It is related to the definition of limits.
'''
Formal definition

Let f(x) and g(x) be two functions defined on some subset of the real 
numbers. One writes

     f(x)=O(g(x))\mbox{ as }x\to\infty\,

if and only if, for sufficiently large values of x, f(x) is at most a 
constant multiplied by g(x) in absolute value. That is, f(x) = O(g(x)) 
if and only if there exists a positive real number M and a real number 
x0 such that

     |f(x)| \le \; M |g(x)|\mbox{ for all }x>x_0.
'''
For g(x) == 1, this reduces to |f(x)| < M for some M (and large x), 
which is to say, f(x) is bounded (at least for large x).

Hmmm. By that definition, 1/x is O(1). Let x0 be anything but 0 and M = 
1/x0. Some might find that disturbing. But it is the nature of the 
notation, as with limit notation, that is says *nothing* about the 
behavior of f for small x.

 > People who have bothered to read ItA will use O(1) and constant
> time interchangeably while talking of the order of growth of the running
> time algorithms

People who have bothered to read the Bidle will use terms the way they 
are used in the Bible. So what? In other words, I do not regard ItA as 
scripture in the way you seem to. (I presume you mean the Cormen, etal 
book. I partially read a library copy over 20 years ago but never 
bothered to buy a copy. I see it is now into its third edition.) If they 
disagree with Knuth and most others (which I would not claim without 
seeing their actual text) then so much the worse for them.

 > and most of those are aware that 'big oh' hides a
> constant, and that in the real world a O(log n) algorithm can outperform
> an O(1) algorithm for small values of n.

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.

>>> Uhm, O(1) /is/ constant time, see page 45 of Introduction to Algorithms,
>>> 2nd edition.

Given that the Wikipedia article references that section also, I wonder 
if it really disagrees with the definition above.

-- 
Terry Jan Reedy