Data structure and time complexity behind iOS Fundation classes like NSMutableArray

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.

References:

• http://ciechanowski.me/blog/2014/03/05/exposing-nsmutablearray/
• https://developer.apple.com/library/ios/documentation/Cocoa/Conceptual/Collections/Articles/Arrays.html

to be continued