Terry Reedy <tjre...@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 -- http://mail.python.org/mailman/listinfo/python-list
