I was looking into Core Foundation and CFDictionary, and in the Apple Documentation I found this,
The access time for a value in a CFDictionary object is guaranteed to be at worst O(log N) for any implementation, but is often O(1) (constant time). Insertion or deletion operations are typically in constant time as well, but are O(N*log N) in the worst cases. It is faster to access values through a key than accessing them directly. Dictionaries tend to use significantly more memory than an array with the same number of values
To my surprise, In CFDictionary source , I found this,
The access time for a value in the dictionary is guaranteed to be at worst O(N) for any implementation, current and future, but will often be O(1) (constant time). Insertion or deletion operations will typically be constant time as well, but are O(N*N) in the worst case in some implementations. Access of values through a key is faster than accessing values directly (if there are any such operations). Dictionaries will tend to use significantly more memory than a array with the same number of values.
Why such difference..? or Am I looking in the wrong place?
Edit: In the apple OpenSource Browser, why are there so many folders which seems like different versions of Core Foundation, is it..? Which out of those is latest/relevant?
"In some implementations". Since you have the source, you can check easily what the worst case is for your implementation. For the worst case, assume that every object in the dictionary returns a hash value of 0 :-)
BTW. Worst case will happen when the hash table gets full and is rebuilt completely. That's why you use at amortised time, not at worst time, unless that worst time for a single insertion is important for you.