# Is the Set.has() method O(1) and Array.indexOf O(n)? [duplicate]

I have seen in an answer that the `Set.has()` method is O(1) and `Array.indexOf()` is O(n).

``````var a = [1, 2, 3, 4, 5];
a.indexOf(5);

s = new Set(a);
s.has(5);              //Is this O(1)?
``````

Is `Set.has()` really O(1) ?

I don’t think the array that has 5 elements is good case to check time complexity.

So based on @Shidersz’s snippet, I made a new one that has many elements and invoked once.

Is Set.has() really O(1) ?

Yes. Time complexity of Set.has() is O(1) according to result of the test below.

``````const MAX = 10000000
let a = []
a.length = MAX

for (let i = 0; i < MAX; i++) {
a[i] = i
}

let s = new Set(a)

let o = a.reduce((acc, e) => {
acc[e] = e
return acc
}, {})

console.time("Test_Array.IndexOf(0)\t")
a.indexOf(0);
console.timeEnd("Test_Array.IndexOf(0)\t")
console.time("Test_Array.IndexOf(n/2)\t")
a.indexOf(MAX / 2);
console.timeEnd("Test_Array.IndexOf(n/2)\t")
console.time("Test_Array.IndexOf(n)\t")
a.indexOf(MAX);
console.timeEnd("Test_Array.IndexOf(n)\t")

console.time("Test_Set.Has(0)\t\t")
s.has(0)
console.timeEnd("Test_Set.Has(0)\t\t")
console.time("Test_Set.Has(n/2)\t")
s.has(MAX / 2)
console.timeEnd("Test_Set.Has(n/2)\t")
console.time("Test_Set.Has(n)\t\t")
s.has(MAX)
console.timeEnd("Test_Set.Has(n)\t\t")

console.time("Test_Object\t\t")
o
console.timeEnd("Test_Object\t\t")
console.time("Test_Object[n/2]\t")
o[MAX / 2]
console.timeEnd("Test_Object[n/2]\t")
console.time("Test_Object[n]\t\t")
o[MAX]
console.timeEnd("Test_Object[n]\t\t")``````
``````.as-console {
background-color: black !important;
color: lime;
}

.as-console-wrapper {
max-height: 100% !important;
top: 0;
}``````

If one read the specification of `has()`, there is an algorithm describing it:

Algorithm for `Set.prototype.has(value)`:

The following steps are taken:

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

And apparently, based on that algorithm and the presence of the word `REPEAT` one can have some confusion about it to be `O(1)` (we could think it could be `O(n)`). However, on the specification we can read that:

Set objects must be implemented using either hash tables or other mechanisms that, on average, provide access times that are sublinear on the number of elements in the collection.

Thanks to @CertainPerformance for pointing this.

So, we can create a test to compare `Array.indexOf()` and `Set.has()` in the worst case, i.e. look for an item that isn’t in the array at all (thanks to @aquinas for pointing this test):

``````// Initialize array.
let a = [];

for (let i = 1; i < 500; i++)
{
a.push(i);
}

// Initialize set.
let s = new Set(a);

// Initialize object.
let o = {};
a.forEach(x => o[x] = true);

// Test Array.indexOf().
console.time("Test_Array.indexOf()");
for (let i = 0; i <= 10000000; i++)
{
a.indexOf(1000);
}
console.timeEnd("Test_Array.indexOf()");

// Test Set.has().
console.time("Test_Set.has()");
for (let i = 0; i <= 10000000; i++)
{
s.has(1000);
}
console.timeEnd("Test_Set.has()");

// Test Object.hasOwnProperty().
console.time("Test_Object.hasOwnProperty()");
for (let i = 0; i <= 10000000; i++)
{
o.hasOwnProperty(1000);
}
console.timeEnd("Test_Object.hasOwnProperty()");``````
``````.as-console {background-color:black !important; color:lime;}
.as-console-wrapper {max-height:100% !important; top:0;}``````

And now we can see that `Set.has()` performs better than `Array.indexOf()`. There is also an extra comparison to `Object.hasOwnProperty()` to take as reference.

# Conclusion:

While `O(1)` complexity isn’t guaranteed, the specification requires the method to run in sublinear time. And `Set.has()`, generally, will perform better than `Array.indexOf()`.

# Another Test:

On next example, we going to generate a random set of sample data and use it later to compare the differents methods.

``````// Generate a sample array of random items.

const getRandom = (min, max) =>
{
return Math.floor(Math.random() * (max - min) + min);
}

let sample = Array.from({length: 10000000}, () => getRandom(0, 1000));

// Initialize array, set and object.

let a = [];

for (let i = 1; i <= 500; i++)
{
a.push(i);
}

let s = new Set(a);
let o = {};
a.forEach(x => o[x] = true);

// Test Array.indexOf().

console.time("Test_Array.indexOf()");
for (let i = 0; i < sample.length; i++)
{
a.indexOf(sample[i]);
}
console.timeEnd("Test_Array.indexOf()");

// Test Set.has().
console.time("Test_Set.has()");
for (let i = 0; i < sample.length; i++)
{
s.has(sample[i]);
}
console.timeEnd("Test_Set.has()");

// Test Object.hasOwnProperty().
console.time("Test_Object.hasOwnProperty()");
for (let i = 0; i < sample.length; i++)
{
o.hasOwnProperty(sample[i]);
}
console.timeEnd("Test_Object.hasOwnProperty()");``````
``````.as-console {background-color:black !important; color:lime;}
.as-console-wrapper {max-height:100% !important; top:0;}``````

Finally I want to apologize for the confusion the first version of my answer could cause. Thanks to all for giving me a better understanding of my mistakes.

Read More:   Async/Await with Vuex dispatch The answers/resolutions are collected from stackoverflow, are licensed under cc by-sa 2.5 , cc by-sa 3.0 and cc by-sa 4.0 .