Search code examples
javascriptarrayssetbig-ocomputer-science

Time complexity (Big-O) of converting an array to a Set

So there is multiple ways to convert an Array to a Set in JS.

Example #2 is definitely O(n) since is iterating through all the elements of the array. is that the same case for Example #1? or JS does do some optimization in the background for us?

If yes, are there any downsides to using Example #1?

Example 1

const arr = [ 1, 3, 2, 3, 5 ];
const set = new Set(arr);

console.log(set);

/*
    Output: Set { 1, 3, 2, 5 }
*/

Example 2

const arr = [ 1, 3, 2, 3, 5 ];    
const set = new Set();
arr.map(item => set.add(item));

console.log(set);

/*
    Output: Set { 1, 3, 2, 5 }
*/
Solution

  • It's still O(n); there's no magical way for JS to put all n elements in the Set without actually iterating through all n elements. The only way to get below O(n) would be to skip some of the elements, which is clearly impossible if all of them must be considered for inclusion in the Set.