CODEWITHSUNDEEP
javascriptarraystime-complexity
Nirdesh Kumar
Nirdesh Kumar

Reputation: 651

Time complexity of the includes method in JavaScript

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?

Upvotes: 35

Views: 40185

Answers (2)

Yury Tarabanko
Yury Tarabanko

Reputation: 45106

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

  1. Let O be ? ToObject(this value).

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

  3. If len is 0, return false.
  4. Let n be ? ToInteger(fromIndex). (If fromIndex is undefined, this step produces the value 0.)
  5. If n ≥ 0, then Let k be n.
  6. Else n < 0, Let k be len + n. If k < 0, let k be 0.
  7. 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).

Upvotes: 24

Nirdesh Kumar
Nirdesh Kumar

Reputation: 651

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

Upvotes: 1

Related Questions