Time complexity of the includes method in JavaScript

Question

I have an array that contains some hash values of certain strings, I don't want duplicate values in my array so I use if logic like this:

if(!arrayOfHash.includes(hash_value)){
  arrayOfHash.push(hash_value); 
}

I want to know the complexity of the includes method in JavaScript. Is it a linear search function or is it a modified search function?

If you write something like this it can be O(n) just one for loop is enough — Gurkan İlleez, Feb 13 '18 at 06:17
ya if it is implemented as a linear search , can i check the internal working of includes() function anywhere ...? — Nirdesh Kumar Choudhary, Feb 13 '18 at 06:20
Also you can check https://developer.mozilla.org/tr/docs/Web/JavaScript/Reference/Global_Objects/Array/includes — Gurkan İlleez, Feb 13 '18 at 06:20
You can do `arrayOfHash = Array.from(new Set(hash_values))` to remove duplicates in O(n) — Patrick Roberts, Feb 13 '18 at 07:59
thanks bro ..so i have to use hashMap (dictionary) to reduce my complexity o(1 ) time ... — Nirdesh Kumar Choudhary, Feb 13 '18 at 10:07

score 22 · Accepted Answer · edited Apr 29 '19 at 16:34

22

Spec describes this function as linear search. Array.prototype.includes

Let O be ? ToObject(this value).

Let len be ? ToLength(? Get(O, "length")).

If len is 0, return false.

Let n be ? ToInteger(fromIndex). (If fromIndex is undefined, this step produces the value 0.)

If n ≥ 0, then Let k be n.

Else n < 0, Let k be len + n. If k < 0, let k be 0.

Repeat, while k < len ... Increase k by 1.

Which is quite a reasonable choice in general case (list is not sorted, list is not uniform, you do not maintain additional datastructures along with the list itself).

edited Apr 29 '19 at 16:34

Misha Brukman

12,938
4
61
78

answered Feb 13 '18 at 07:51

Yury Tarabanko

44,270
9
84
98

1

That line 7 you put in bold implies it is a loop **"Repeat, while k < len ... Increase k by 1."**. And it states above "The optional second argument fromIndex defaults to +0 (i.e. the whole array is searched)" so I think that means O(n). How are you getting O(1)? – garrettmac Jan 19 '22 at 19:17
2

@garrettmac Linear search is `O(n)` right. I am not saying it is `O(1)`. What makes you think so, BTW? – Yury Tarabanko Jan 19 '22 at 19:24
@garrettmac have you, by accident, looked at the second answer here? O(n), as I am sure you are aware, is linear time, and O(1) is constant time, and nowhere does Yury say that the search has O(1) time complexity... – Oleg Valter is with Ukraine Jan 19 '22 at 19:36
1

Y’all are 100% right, I feel silly now. Thank you for correcting me. – garrettmac Jan 20 '22 at 04:28

score 1 · Answer 2 · answered Feb 13 '18 at 10:15

as my list is not sorted so i have create a dictionary and put values into it after checking if value present in it or not . Here in this dictionary my value and key are same .

var   arrayOfHashMap = {};/*is a dictionary,arrayOfValue is a list*/
    if(arrayOfHashMap[hash_value] !=hash_value){
                               arrayOfValue.push(hash_value); 
                               arrayOfHashMap[hash_value]=hash_value;
                        }

in this case I search values in o(1) time and put them in arrayOfValue

Time complexity of the includes method in JavaScript

2 Answers2

Linked