Data structure and time complexity behind iOS Fundation classes like NSMutableArray
NSMutableArray probably uses circular buffer (ref 1).
From Apple guide (ref 2) — Note: Most operations on an array take constant time: accessing an element, adding or removing an element at either end, and replacing an element. Inserting an element into the middle of an array takes linear time.
to be continued