This is in regards to a debate I had with an interviewer when I was interviewing at Amazon.

Let's I create an object:

var Obj = {};
Obj['SomeProperty'] = function ( ) { console.log("Accessed some property"); };
Obj[69] = true;

Is there anything in the JavaScript guaranteeing that when I subsequently access those 2 properties like Obj['SomeProperty'] and Obj[69] the respective values function ( ) { console.log("Accessed some property"); }; and 69 are looked up in O(1) time? I know the access operator [] gives a seasoned programmer the impression that he's dealing with an O(1) lookup structure, but can't it be possible for a JavaScript engine to implement Object in a way such that properties are not looked up in O(1)?

This is in regards to a debate I had with an interviewer when I was interviewing at Amazon.

Let's I create an object:

var Obj = {};
Obj['SomeProperty'] = function ( ) { console.log("Accessed some property"); };
Obj[69] = true;

Is there anything in the JavaScript guaranteeing that when I subsequently access those 2 properties like Obj['SomeProperty'] and Obj[69] the respective values function ( ) { console.log("Accessed some property"); }; and 69 are looked up in O(1) time? I know the access operator [] gives a seasoned programmer the impression that he's dealing with an O(1) lookup structure, but can't it be possible for a JavaScript engine to implement Object in a way such that properties are not looked up in O(1)?

• javascript
• data-structures
• time-plexity
• plexity-theory

• Map access is typically O(log(n)) - not sure why you say it is O(1) ? As per developer.mozilla/en-US/docs/Web/JavaScript/Guide/…, Objects are referred to as "associative arrays" – Wand Maker Commented Dec 15, 2015 at 14:48
• 2 A JavaScript engine can implement anything any way it wants, but if you get into that kind of territory then you may as well consider that we all use pre-emptive OS', so nothing of anything very much is really GUARANTEED in relation to real time then, even without considering what might not be guaranteed from running code on someone elses browser! Chances are slim that the JS implementation running your code is so poor that its major features will be suboptimal by an order of plexity though. – Michael Commented Dec 15, 2015 at 14:53
• Agreed with @Michael. Very much this - if you can't trust the platform upon which you stand, then you can't really trust anything. It's definitely possible to build an engine that is as inefficient as possible - in fact, it's possible to build an engine that hangs, meaning it just plain doesn't work, which would satisfy the inefficiency clause. At some point, you just have to assume that it's turtles all the way down. – user677526 Commented Apr 30, 2016 at 6:11

1 Answer 1

Is there anything in the JavaScript guaranteeing that the values are looked up in O(1) time?

No. JavaScript does not give any plexity guarantees whatsoever, except for ES6 collections.

I know the access operator [] gives a seasoned programmer the impression that he's dealing with an O(1) lookup structure

Yes you are, this is a reasonable expectation. Engines employ all kinds of optimisations, from hidden classes over hashmaps to dynamic arrays, to meet these assumptions.

Of course, never forget that JS objects are plex beasts, and accessing a simple property might trigger a getter trap that in turn could do anything.

Can't it be possible for a JavaScript engine to implement Object in a way such that properties are not looked up in O(1)?

Yes, that's possible.