What is the runtime of array.length? [duplicate]

Question

This question already has answers here:

time complexity or hidden cost of <Array Name>.length in java (5 answers)

Closed 6 years ago.

Let's say I have an array:

int[] array = new int[10];

What is the runtime of:

int len = array.length;

I would think that this would be a constant time operations, but today in an interview, the interviewer told me that this would be O(n) because the number of elements would need to be counted.

Additionally, if I have a loop like this:

for (int i = array.length - 1; i >=0; i--) {
    something with array[i];
}

Does this entail an extra n operations to get to the end of the array to start the loop? The interviewer came from a C background, so maybe they were mistaken about how Java works, but I didn't want to push it during the interview.

Answer 1

It is a constant time operation in all of JAVA implementations because JVM has to store this field to check index (it has to throw IndexOutOfBoundsException if index is invalid ).

It might be a good idea to cache array length in local variable because JVM stack access is faster but this improvement is very minor, normally loop body execution will overweight this optimization.

Answer 2

Here's another SO thread that explains the implementation of array.length:

How is length implemented in Java Arrays?

Calling the length property is an O(1) operation, because it doesn't actually count the array, that field is set when the array is created.

Your loop, on the other hand, is an O(n) operation.

Answer 3

array.length is O(1) and the loop is O(n) overall (assuming the "something" is constant-time).

Is it different for c?

C is different in that, depending on how the array is allocated, you can either find out its size in O(1) time or not at all. By "not at all" I mean that you have to keep track of the size yourself.

(On a personal note, if that's the caliber of interviewers, I would have reservations about coming to work there.)