Time complexity of JavaScript's array.length

What is the time complexity of a call to array.length in JavaScript? I think it would constant since it seems that property is set automatically on all arrays and you're just looking it up?

Solution 1:

I think it would be constant since it seems that property is set automatically on all arrays and you're just looking it up?

Right. It's a property which is stored (not calculated) and automatically updated as necessary. The specification is explicit about that here and here amongst other places.

In theory, a JavaScript engine would be free to calculate length on access as though it were an accessor property as long as you couldn't tell (which would mean it couldn't literally be an accessor property, because you can detect that in code), but given that length is used repeatedly a lot (for (let n = 0; n < array.length; ++n) springs to mind), I think we can assume that all JavaScript engines in widespread use do what the spec says or at least something that's constant time access.

Just FWIW: Remember that JavaScript's standard arrays are, in theory, just objects with special behavior. And in theory, JavaScript objects are property bags. So looking up a property in a property bag could, in theory, depend on how many other properties are there, if the object is implemented as some kind of name->value hashmap (and they used to be, back in the bad old days). Modern engines optimize objects (Chrome's V8 famously creates dynamic classes on the fly and compiles them), but operations on those objects can still change property lookup performance. Adding a property can cause V8 to create a subclass, for instance. Deleting a property (actually using delete) can make V8 throw up its hands and fall back into "dictionary mode," which substantially degrades property access on the object.

In other words: It may vary, engine to engine, even object to object. But if you use arrays purely as arrays (not storing other non-array properties on them), odds are you'll get constant-time lookup.

Solution 2:

It doesn't seem like a bottleneck but if you want to be sure use var len = arr.length and check that. It doesn't hurt and seems to be a tad faster on my machine albeit not a significant difference.

var arr = [];
for (var i = 0; i < 1000000; i++) {
  arr[i] = Math.random();
}


var start = new Date();
for (var i = 0; i < arr.length; i++) {
   arr[i] = Math.random(); 
}

var time1 = new Date() - start;
var start = new Date();

for (var i = 0, len = arr.length; i < len; i++) {
  arr[i] = Math.random();
}

var time2 = new Date() - start;

document.getElementById("output").innerHTML = ".length: " + time1 + "<br/>\nvar len: " + time2;

<div id="output"></div>