Consistency

[Meta via Digitalmars-d]

On Sunday, 15 February 2015 at 18:20:10 UTC, Xinok wrote:
> On Sunday, 15 February 2015 at 18:15:13 UTC, Meta wrote:
>> On Sunday, 15 February 2015 at 17:18:08 UTC, Steve D wrote:
>>> Python (built-in)
>>>
>>> dict1 = {"a":1,"b":2}
>>> tup1  = (0,1,2,3)
>>> arr1  = [0,1,2,3]  # list type
>>> str1  = "abcd"
>>>
>>> print "b" in dict1    # True
>> O(1) lookup
>
> A small nitpick, but I'm sure that should be O(log n). 
> Dictionaries don't have constant lookup time.

Oh, whoops. I mixed up average-case complexity with worst-case. 
Although, isn't lookup O(n) in the worst case for hash tables?