1

I know that for Object.keys the time complexity would be O(n) as each key is in the object is returned. But when using a Map.prototype.keys, an iterator function is return and not all of the keys. I was wondering is this O(n) or O(1)

Daniel Kobe
  • 9,376
  • 15
  • 62
  • 109

1 Answers1

0

Yes, it is O(1). The returned iterator is live, it doesn't collect all keys at the time of the call.

Of course consuming all items from the iterator is obviously O(n), so it doesn't really matter in the end.

Bergi
  • 630,263
  • 148
  • 957
  • 1,375
  • Wouldn't this be implementation specific or does the JavaScript spec go so far as to prescribe the implementation. – bhspencer Apr 04 '18 at 19:53
  • @bhspencer The spec doesn't spell out any complexity guarantee here, but it does define the live behaviour and sets the obvious performance expectation through that. – Bergi Apr 04 '18 at 19:58
  • @Bergi, I've been working on how to get the first item from the map in O(1) time. Since we don't have access to the first item as we would if it were an array (myArray[0]), the only other way would be to start to iterate over each item in the map, assign the 1st item to a variable and immediately break out of the loop after that first iteration. If the "returned iterator is live" when we do something like myMap.entries(), then do you believe something like the below code would still retrieve the first item in O(1): let val; for (const [key, value] of m.entries()) { val = key; break;} – charlitos Feb 09 '22 at 16:01
  • @Bergi, something like the following would also retrieve the first value from the map in O(1) time? [val] = myMap.keys(); – charlitos Feb 09 '22 at 16:21
  • 1
    @charlitos [yes](https://stackoverflow.com/q/32373301/1048572) – Bergi Feb 09 '22 at 19:50