7

Set has contains function which returns true if member exists in the set; otherwise, false.

and its complexity is O(1).

I want to know how its complexity is constant O(1) i.e. it does not depends on size

Here are the docs : https://developer.apple.com/documentation/swift/set/1540013-contains

Haris
  • 1,822
  • 2
  • 22
  • 44
  • 2
    Who says that the complexity is O(1)? It strongly depends on the distribution of the hash values of the elements. – Martin R May 08 '18 at 19:02
  • 3
    @MartinR Who says? [The documentation.](https://developer.apple.com/documentation/swift/set/1540013-contains) If that's incorrect, a documentation bug report should be filed. – Charles Srstka May 08 '18 at 19:24
  • docs link added in question – Haris May 08 '18 at 19:36
  • Disclaimer: it's at the bottom, under the code example. – Tamás Sengel May 08 '18 at 19:37
  • @CharlesSrstka it's not O(1) on every iteration. It's O(1) *on average*, assuming that you have a good hash function. See discussion [here](https://stackoverflow.com/questions/2771368/can-hash-tables-really-be-o1) and [here](https://stackoverflow.com/questions/4363539/how-does-hashing-have-an-o1-search-time), also [this proposal](https://github.com/apple/swift-evolution/blob/master/proposals/0206-hashable-enhancements.md) for improvement to Swift `hashValue`. – Code Different May 08 '18 at 19:41
  • [Dictionary.swift](https://github.com/apple/swift/blob/master/stdlib/public/core/Dictionary.swift) mentions that *"Native storage is a hash table with open addressing and linear probing."* and I think the same is true for `Set`. If all elements have the same hash value then the lookup degenerates to O(N). – Martin R May 08 '18 at 19:57
  • 1
    @CodeDifferent I'm not taking a stand on whether it's O(1) or not. I'm pointing out that the documentation _states_ it's O(1), and that if this is demonstrably untrue, then someone should file a report against the documentation. Because as long as the documentation claims the complexity is O(1), it's not unreasonable to assume the complexity will be O(1). – Charles Srstka May 08 '18 at 21:31

1 Answers1

4

It will use hash function to insert, search. Good hash function will lead to 0(1) time complexity. https://en.wikipedia.org/wiki/Hash_table

RaviYadav
  • 97
  • 1
  • 7