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

user_5262452 0
Viewed 1928

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 }
*/
computer-science big-o set arrays javascript
1 Answers

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.

user_3646960
Related