Performance: sets vs dicts.

[Arnaud Delobelle]

Terry Reedy <tjreedy at udel.edu> writes:

> On 9/1/2010 8:11 PM, John Bokma wrote:
[...]
>>>> 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.

In simple terms, O(1) is *bounded* time.

This is not the same as constant, even though it is true that the
misleading expression "constant time" is widely used.  I emphasized the
difference as you seemed to say that describing list element access as
O(1) was misleading because for example accessing contiguous elements
would be significantly faster that accessing distant ones.  This may or
may not be the case, but it remains true that this time is bounded and
this is what O(1) really means.

-- 
Arnaud