title: What is the data structure behind NSMutableArray?
body: <p>Usually, a "mutable array" class is implemented as a wrapper around a simple array. The wrapper allocates more memory when you add an element past the end. This is a common data structure and the performance of the various operations is well known. You get O(1) element access, O(N) insert and remove, or O(1) (on average) insert and remove at the end of the array. But <code>NSMutableArray</code> is something else.  For example the <a href="https://developer.apple.com/library/mac/documentation/Cocoa/Conceptual/Collections/Articles/Arrays.html" rel="noreferrer">docs</a> say [emphasis mine]:</p>
  
  <blockquote>
    <p>Note: Most operations on an array take <strong><em>constant time</em></strong>: accessing an element, adding or removing an element <strong><em>at either end</em></strong>, and replacing an element. Inserting an element into the middle of an array takes linear time.</p>
  </blockquote>
  
  <p>So, what exactly is <code>NSMutableArray</code>?  Is this documented somewhere?  </p>