0

What are the big O notations of Javascripts Map.prototype.has and Set.prototype.has methods?

According to the documentation for Set:

The following steps are taken:

  1. Let S be the this value.
  2. If Type(S) is not Object, throw a TypeError exception.
  3. If S does not have a [[SetData]] internal slot, throw a TypeError exception.
  4. Let entries be the List that is the value of S’s [[SetData]] internal slot.
  5. Repeat for each e that is an element of entries,
    • If e is not empty and SameValueZero(e, value) is true, return true.
  6. Return false.

The description makes Set sound like it is looping through an array, as opposed to retrieving the result in constant time.

The description of Map.prototype.has is almost the same as well. Thus, what is the big O notation of Map.prototype.has and Set.prototype.has?

Is one faster than the other?

user3554664
  • 349
  • 2
  • 16
  • "*The description makes Set sound like it is looping through an array*" - not exactly. The description only *specifies* that whatever actual implementation is used, it needs to *behave as if* it was looping through the list of entries. – Bergi Oct 25 '17 at 03:01
  • Its `O(log(n))` or better. – Lux Oct 25 '17 at 03:02

0 Answers0