Complexity of insertObject:atIndex:

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

Also, ho开发者_如何学运维w can I find out the complexity of various Objective-C statements?

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.

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.

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

Just a nit pick: NSArray or CFArray is not a part of the language, it’s a Core Foundation class. You can take a look at CFArray source code to reason about its complexity, but it looks like it would take a while :) If you are concerned about real-world performance (as opposed to asking from a theoretical point of view), do a test and profile.

The official documents don't state it, but I guess it is similar to array lists in other languages, which would be O(n).