Menu
Anyone know the time-complexity of ECMAScript5's Object.keys() in common implementations? Is it O(n) for n keys? Is time proportional to the size of the hash table, assuming a hash implementation?
I'm looking for either guarantees by language implementors or some real world benchmarking.
916
That's why O(n/2) = O(n). So the linear lookup has O(n) time complexity.
The reason that objects have a constant run-time is due to the fact that they are unordered data structures. Moreover, when we add, remove, or access elements, we do so based on their keys, not their location, so we can make changes without impacting the other key/value pairs.
Description. Object. keys() returns an array whose elements are strings corresponding to the enumerable properties found directly upon object . The ordering of the properties is the same as that given by looping over the properties of the object manually.
Objects are stored in the for of a key/value pair {key: value}. JavaScript objects are implemented using Hash tables under the hood. One thing about Hashing table is that — Hash tables Retrieve method have O(1), constant time complexity because of the use of a hashing function.
It appears to be O(n) in V8 (chrome, node.js) at least:
> var hash = {} > , c = 0; > > var s = +new Date();Object.keys(hash);console.log(+new Date() - s); 0 > for(var i=0; i<100000; i++, c++){ hash[c] = 1; } > var s = +new Date();Object.keys(hash);console.log(+new Date() - s); 26 > for(var i=0; i<100000; i++, c++){ hash[c] = 1; } > var s = +new Date();Object.keys(hash);console.log(+new Date() - s); 49 > for(var i=0; i<100000; i++, c++){ hash[c] = 1; } > var s = +new Date();Object.keys(hash);console.log(+new Date() - s); 75 > for(var i=0; i<100000; i++, c++){ hash[c] = 1; } > var s = +new Date();Object.keys(hash);console.log(+new Date() - s); 102 If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
