Does anyone know the complexity of Object.entries() in Javascript? Based on this question I’d guess at maybe O(n) as well if it’s implemented by obtaining the keys and values as arrays then zipping them together?
Advertisement
Answer
(V8 developer here.)
Short answer: yes, the complexity of Object.entries() is O(n) in most cases.
For large objects (thousands of properties), it is O(n log n). That’s because we store the properties of large objects (as well as certain “complicated” small objects) in a dictionary, and while retrieving all keys from that dictionary has O(n) complexity, Object.entries() is specified to return entries in property creation order, so we have to sort them, which is an O(n log n) operation.
(This is true for Object.keys() too; the question/answer you’ve linked is incorrect in that respect.)
Also, keep in mind that since an array must be allocated for every entry, Object.entries() leaves behind quite a lot of garbage when used on large objects. (That doesn’t change its complexity class though.)
There’s another wrinkle, which may be more relevant: retrieving a property’s value can mean invoking a getter, and that getter really can do anything, in which case all bets are off. It might not even terminate at all:
var o = {};
Object.defineProperty(o, "there's nothing O(n) about this",
{get: () => { while (true); }, enumerable: true});
console.log(Object.entries(o));