Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

Tags:

java

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.

like image 882
fvrghl Avatar asked Feb 06 '14 21:02

fvrghl


2 Answers

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.)

like image 186
NPE Avatar answered Nov 18 '22 23:11

NPE


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.

like image 33
jbaliuka Avatar answered Nov 18 '22 23:11

jbaliuka