Complexity of insertObject:atIndex:

Question

What is the complexity of -[NSArray insertObject:atIndex:] -- N? or constant?

Also, how can I find out the complexity of various Objective-C statements?

Answer 1

There is a discussion here and CFArray.h source code states:

Computational Complexity
The access time for a value in the array is guaranteed to be at worst O(lg N) for any implementation, current and future, but will often be O(1) (constant time). Linear search operations similarly have a worst case complexity of O(Nlg N), though typically the bounds will be tighter, and so on. Insertion or deletion operations will typically be linear in the number of values in the array, but may be O(Nlg N) clearly in the worst case in some implementations. There are no favored positions within the array for performance; that is, it is not necessarily faster to access values with low indices, or to insert or delete values with high indices, or whatever.

Answer 2

Interestingly, the performance of arrays in Foundation depends on the size of the array.

I don't think there's any site that spells out the performance of all the data structures in Foundation, but the linked article gives a nice observational analysis that you could repeat for other containers such as NSMutableDictionary.

Answer 3

there really is no matrix (afaik), but this post should help explain why as well as answer the question in the subject:

http://ridiculousfish.com/blog/archives/2005/12/23/array/index.html