You can get an idea of the computational complexity of Apple data structures by looking at comments in the headers of their Core Foundation bridge equivalents (since they essentially use the same code under the hood).
Interestingly, the time complexity of CFArray is not really guaranteed to be O (n):
Computational complexity
The access time for the value in the array is guaranteed to be the worst O (log N) for any implementation, current and future, but it will often be O (1) (constant time). Linear search operations likewise have worse O (N * lg N) complexity, although usually the boundaries will be stricter, etc. Insert or delete operations will usually be linear in the number of values in the array, but there may be O (N * log N) explicitly in the worst case in some implementations. There are no favorable positions in the array for performance; that is, it’s not necessary to access values with low indices faster or insert or delete values with high indices or whatever.
These temporary difficulties suggest that CFArray (and therefore NSArray ) can actually be implemented as a tree (tests show that it can even switch between several basic data structures).
Similarly, for CFDictionary above estimates have a fairly wide range:
Computational complexity
The access time to the value in the dictionary is guaranteed the worst O (N) for any implementation, current and future, but it will often be O (1) (constant time). Insert or delete operations will usually also be constant, but are O (N * N) for the worst case in some implementations. Access to values via a key is faster than direct access to values (if there are such operations). Dictionaries will use significantly more memory than an array with the same number of values.
I could not find a similar comment in the Core Foundation headers for CFSet , but checking the source code shows that it is based on CFBasicHash , which is a hash table, so the time complexity will be typical of a hash table - O (1) insertion, deletion and testing , and O (n) in the worst case.
If you're really interested in learning how these data structures work, Core Foundation is open source, so you can read the source code on the Apple website .