What is the big-O notation for iteration through NSSet and NSDictionary

Question

I was wondering what is the big-O notation for iteration through NSSet. The answer for an NSArray is obviously O(n) - but what is the answer for NSSet? Also - I'm assuming the same answer would apply for NSDictionary?

Answer 1

You can get some idea of the computational complexity of Apple's data structures by looking at the comments in the headers of their bridged Core Foundation equivalents (as they are essentially using the same code under the hood).

Interestingly, the time complexity of CFArray is not actually guaranteed to be O(n):

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(N*lg 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(N*lg 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.

These time complexities suggest that CFArray (and therefore NSArray) might actually be implemented as a tree (tests show that it might even be switching between multiple underlying data structures).

Similarly for CFDictionary, the bounds given have quite a broad range:

Computational Complexity

The access time for a value in the dictionary is guaranteed to be at worst O(N) for any implementation, current and future, but will often be O(1) (constant time). Insertion or deletion operations will typically be constant time as well, but are O(N*N) in the worst case in some implementations. Access of values through a key is faster than accessing values directly (if there are any such operations). Dictionaries will tend to use significantly more memory than a array with the same number of values.

I was not able to find a similar comment in the Core Foundation headers for CFSet, but inspection of the source code shows that it's based on CFBasicHash, which is a hash table, so the time complexity would be as typical for a hash table — O(1) insertion, removal and testing typically, and O(n) in the worst case.

If you're really interested in finding out exactly how these data structures work, Core Foundation is open source, so you can read the source code on Apple's website.