title: Time complexity of array.prototype.includes vs. set.prototype.has
body: <p>I've been reading conflicting answers about modern javascript engines' time complexity when it comes to sets vs arrays in javascript.</p>
  <p>I completed the demo task of codility, which is a simple assignment to find a solution for the following: given an array A of N integers, return the smallest positive integer (greater than 0) that does not occur in A.</p>
  <p>For example, given A = [1, 3, 6, 4, 1, 2], the function should return 5.</p>
  <p>My first solution was:</p>
  <pre><code>const solution = arr =&gt; {
      for(let int = 1;;int++) {
          if (!arr.includes(int)) {
              return int;
          }
      }
  }
  </code></pre>
  <p>Now, the weird thing is that codility says this solution has a time complexity of O(n**2) (they prefer a solution of complexity O(n). As far as I know, array.prototype.includes is a linear search (<a href="https://tc39.es/ecma262/#sec-array.prototype.includes" rel="nofollow noreferrer">https://tc39.es/ecma262/#sec-array.prototype.includes</a>) meaning it should have an O(n) time complexity.</p>
  <p>If I enter a different solution, using a Set, I get the full score:</p>
  <pre><code>const solution = arr =&gt; {
    const set = new Set(arr);
    let i = 1;
  
    while (set.has(i)) {
      i++;
    }
  
    return i;
  }
  </code></pre>
  <p>Codility says this apparently has a time complexity of O(N) or O(N * log(N)).</p>
  <p>Is this correct? Is array.prototype.includes in fact O(n**2) instead of O(n)?</p>
  <p>Lastly, I'm a bit confused as to why Set.has() is preferred as in my console performance tests, Array.includes() is consistently outperforming the solution to first create a Set and then looking it up on the set, as can be seen in the following snippet.</p>
  <p><div class="snippet" data-lang="js" data-hide="false" data-console="true" data-babel="true">
  <div class="snippet-code">
  <pre class="snippet-code-js lang-js prettyprint-override"><code>const rand = (size) =&gt; [...Array(size)].map(() =&gt; Math.floor(Math.random() * size));
  
  const small = rand(100);
  const medium = rand(5000);
  const large = rand(100000);
  
  const solution1 = arr =&gt; {
    console.time('Array.includes');
    for(let int = 1;;int++) {
      if (!arr.includes(int)) {
        console.timeEnd('Array.includes');
        return int;
      }
    }
  }
  
  const solution2 = arr =&gt; {
    console.time('Set.has');
    const set = new Set(arr);
    let i = 1;
    while (set.has(i)) {
      i++;
    }
    console.timeEnd('Set.has');
    return i;
  }
  
  console.log('Testing small array:');
  solution1(small);
  solution2(small);
  console.log('Testing medium array:');
  solution1(medium);
  solution2(medium);
  console.log('Testing large array:');
  solution1(large);
  solution2(large);</code></pre>
  </div>
  </div>
  </p>
  <p>If a set lookup has better time complexity (if that's true) and is preferred by codility, why are my performance tests favoring the array.prototype.includes solution?</p>