I am trying to calculate the time complexity of this particular line in one of my functions:

return [...cache.keys()].sort((a, b) => a - b);

This line is supposed to return a sorted Array of the Map's (cache) keys. I know that Array.prototype.sort() has O(n log n) time complexity. What is the time complexity of Map.prototype.keys()?

CodePudding user response：

Creating the iterator is O(1), iterating all entries and creating an array from them is linear in the size of the collection - O(n).

Depending on the implementation, the number of recently deleted entries might have an impact, but it never should be large enough to change the time complexity to become non-linear.