28

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?

Adam Michalik
  • 9,678
  • 13
  • 71
  • 102
devdropper87
  • 4,025
  • 11
  • 44
  • 70
  • 2
    If I may, why is the time complexity of an object property of concern? It seems so, minimal? – Sterling Archer Sep 29 '15 at 17:54
  • 2
    @SterlingArcher any time complexity is important, so that the final time complexity can be compared to other solutions complexity. – KeitelDOG Apr 18 '19 at 21:09
  • 2
    @KeitelDOG if you're calculating the time complexity of object props you either like pain or your boss hates you – Sterling Archer Apr 18 '19 at 22:10
  • 1
    @SterlingArcher In this case I agree because that is object prop. But more because it's out of our control than because it's minimal. – KeitelDOG Apr 19 '19 at 17:20

2 Answers2

32

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.

T.J. Crowder
  • 1,031,962
  • 187
  • 1,923
  • 1,875
  • in brief does this mean that i don't have to save the array length in a variable and refer it like `(let n = 0; n < arrLen; ++n)`. using `(let n = 0; n < array.length; ++n)` is fine? – cmgchess Apr 16 '23 at 16:03
  • 1
    @cmgchess - Pretty much, yeah. Technically, if you save it to a variable (even better, a `const`) you're avoiding a property access on each loop, which *very slightly* speeds up the loop. But the savings there is likely washed out by whatever you're doing *in* the loop, and you'd have to be looping over a huge array. With today's engines, it's probably premature optimization. :-) Just for fun, I put [this](https://jsfiddle.net/tjcrowder/pt4s9j7w/) together. While there is an effect, it's ***really*** small in modern JS engines. :-) – T.J. Crowder Apr 16 '23 at 17:42
  • 1
    Of course, sometimes it matters *semantically* (e.g., if your'e changing the length of the array), but I know you know that. :-) – T.J. Crowder Apr 16 '23 at 17:59
5

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>
wolfhammer
  • 2,641
  • 1
  • 12
  • 11