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?

Cloudland

If you care about performance, make sure you use "fast enumeration" or blocks. Do not use a regular C for or while loop. developer.apple.com/library/ios/documentation/Cocoa/Conceptual/… – Hornsby

This questions is more of a curiosity topic than an actual question – Cloudland

I see. Well, then the answer depends on what is in the set. NSSet is not a simple class, I wouldn't be surprised if the implementation is tens of thousands thousand lines of code. For starters, there isn't even a real class called "NSSet". That's just a name used to join all of the real classes that go into sets, which class is actually used will change depending on the contents of the set and the patterns your code uses to access the set. In general, a set with 5 items will have vastly different performance characteristics to a set with 5 billion items. And yes, it can handle that much data. – Hornsby

Also, NSSet can provide a wrapper around CFSet — and in that case you have the option of providing your own code to perform data storage/access. Whether or not it's O(n) will depend on the code you wrote in that case. Or perhaps the code written by a third party library or Apple. If you didn't create the "NSSet" yourself, you don't know whether or not it is a CFSet with weird/undocumented performance characteristics. In general, NSSet has excellent performance for a collection of items where the sort order is irrelevant. It's faster than NSArray in many operations, and slower in others. – Hornsby

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.

String

Interesting the header for iOS 16.1 still contains the info about O(N) - worst case while the documentation has another description: The access time for a value in a CFDictionary object is guaranteed to be at worst O(log N) for any implementation, but is often O(1) (constant time). developer.apple.com/library/archive/documentation/… – Netherlands

The perils of non-compiler-checked documentation :’) – String