title: Computational Complexity of CFDictionary
body: <p>I was looking into Core Foundation and CFDictionary, and in the <a href="https://developer.apple.com/library/mac/documentation/CoreFoundation/Conceptual/CFCollections/Articles/types.html#//apple_ref/doc/uid/20001129-CJBEJBHH" rel="nofollow">Apple Documentation</a> I found this,</p>
  
  <blockquote>
    <p>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</p>
  </blockquote>
  
  <p>To my surprise, In <a href="http://opensource.apple.com/source/CF/CF-855.17/CFDictionary.h" rel="nofollow">CFDictionary source</a> , I found this,</p>
  
  <blockquote>
    <p>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.</p>
  </blockquote>
  
  <p>Why such difference..? or Am I looking in the wrong place?</p>
  
  <p>Edit: In the <a href="http://opensource.apple.com/source/CF/" rel="nofollow">apple OpenSource Browser</a>, why are there so many folders which seems like different versions of Core Foundation, is it..? Which out of those is latest/relevant?</p>