CODEWITHSUNDEEP
javascriptdictionarydata-structuresecmascript-6time-complexity
Karan
Karan

Reputation: 817

What is the time complexity of Map.prototype.keys()?

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()?

Upvotes: 1

Views: 666

Answers (1)

Bergi
Bergi

Reputation: 664620

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.

Upvotes: 4

Related Questions