2

What is the time complexity of Set.indexOf? The documentation doesn't say, and the source delegates to some kind of internal storage class (_VariantStorage/_VariantSetStorage) whose source I can't find.

phu
  • 1,199
  • 2
  • 10
  • 20

1 Answers1

4

The documentation for CollectionType suggests that it is O(self.count).

That would make sense, as the worst case scenario is that every element in the Set (or any other collection) is checked for equality. It shouldn't ever be more complex than O(self.count).

Aaron Rasmussen
  • 13,082
  • 3
  • 42
  • 43
  • 4
    That applies to the default implementation, but `Set` provides its own. And depending on how `Set.Index` works, it would make sense for `Set` to be able to provide an `O(1)` implementation, since the whole point of sets is constant-time lookup. – phu Mar 25 '16 at 00:15
  • Take a look at this answer regarding complexity of hash tables generally which suggests that indeed O(n) is worst case scenario, with O(1) being possible, but not guaranteed: http://stackoverflow.com/questions/9214353/hash-table-runtime-complexity-insert-search-and-delete – Aaron Rasmussen Mar 25 '16 at 00:31
  • 2
    After more research, I found that the source for `_VariantSetStorage` is actually in the same file; I just didn't find it with Search because of the GYB macro stuff. Based on that, I believe that while your answer is technically correct, a more thorough version would be: `O(1)` average for a native `Set`, `O(n)` average for a wrapped `NSSet`, and `O(n)` worst-case for both (due to hash collisions). – phu Mar 25 '16 at 18:40