What would be the time complexity of Array.from(). For example:
const set = new Set();
set.add('car');
set.add('cat');
set.add('dog');
console.log(Array.from(set)); // time complexity of making this convertion from Set to Array
2 Answers
It's O(n). When used on an iterable (like a Set), Array.from iterates over the iterable and puts every item returned into the new array, so there's an operation for every item returned by the iterable.
answered Dec 4, 2019 at 9:45
3 Comments
PHP Guru
That doesn't necessarily mean that it's O(n) though. The time complexity depends on the internal implementation so it could be O(n log n) if internally it uses something like Array.prototype.push to add elements to the returned array. That would be a stupid way to implement that, but until I see otherwise I am assuming the worst. And that would also explain why it is so slow.
CertainPerformance
Personally, I feel safe assuming that, when the amount of data is large enough for complexity to have any visible effect, the writers of the various modern JS engines do not choose to use a stupidly inefficient algorithm. It wouldn't be theoretically impossible for someone to go with such an algorithm, but it would be an extremely odd decision to make (except when weird edge cases are involved, in which case all bets are off anyway)
PHP Guru
I'm fairly certain now that the time complexity is indeed O(n log n) because I did a benchmark and it's no faster using Array.from() than it is to just create an array of size 0 and then call Array.prototype.push on it 16 million times. Here's to hoping this gets fixed in future releases of JavaScript.
It is always going to be O(n) as the number of iterations would be directly proportional to the number of elements in the set. Actual Time complexity would be O(n) for retrieving values from a set O(n) for pushing into an array.
O(n) + O(n) = O(2n)
But since we do not consider a constant value when calculating using n value it should be O(n).
Array.from()has a different "problem"; it's quite slow compared to other methods to create that Array. This seems to be due to the overhead generated by the wide variety of input types that the method may have to deal with. So for small data-structures this overhead may outweigh the execution time of the actual task at hand.