# How can a set offer better search performance than an array

While reading the following tutorial on iOS development Working with Foundation (section on Sets near the bottom), I came across the following statement: "Because sets don’t maintain order, they offer faster performance than arrays do when it comes to testing for membership."

The author doesn't mention the underlying data structure and as it stands, I don't see how the second part of this statement can be inferred from the first.

If the NSSet class is implemented using a hash table, I agree that it will have faster lookup performance than an NSArray class but in principle both classes could be implemented using arrays, in which case both would have a lookup performance of O(n).

Am I missing something or is this just an incomplete statement?

• You're right, no such inference can be made. You should read the sentence as: "when we implement sets we can do funky stuff that we can't when implementing arrays, because we need to keep the order of elements in an array intact." For instance, a set could be implemented as some sort of a balanced tree to give you logarithmic membership testing. With arrays it would be linear. But you can't know until you actually look at what they did in NSSet and NSArray. Jun 30 '15 at 17:03
• I believe the point is that, since sets don't have to remember order, they can be implemented using a datastructure that allows fast membership testing. The fact that you could implement sets in a bad way (using arrays) that has bad performance isn't really relevant. Jun 30 '15 at 17:05
• In other words, this is an incomplete statement. Better would be to edit it as "... they might offer faster performance...". Jun 30 '15 at 18:30
• In sorted arrays, we have logarithmic membership tests. In bitvector representations. too. You need to clarify how you want to use sets, and what operations you want to compare. The typical scenario is that set implementations do some things well and some things badly.
– Raphael
Jun 30 '15 at 21:04
• Welcome to SE Computer Science. This statement is correct, imho, if "faster" is understood non strictly, i.e., as "non slower". Otherwise it is a "non sequitur". Jun 30 '15 at 22:05