13

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.

fvrghl
  • 3,642
  • 5
  • 28
  • 36
  • 9
    It's O(1) since this meta-data is saved into the array object. – Nir Alfasi Feb 06 '14 at 21:22
  • @alfasin Yeah, that's what I thought. Is it different for c? – fvrghl Feb 06 '14 at 21:22
  • no - it's the same for all languages. – Nir Alfasi Feb 06 '14 at 21:23
  • Even though the following link is specific for IBM version of the JVM - it can give you a basic idea of how an array is represented in the memory: http://www.ibm.com/developerworks/opensource/library/j-codetoheap/index.html#N10171 – Nir Alfasi Feb 06 '14 at 21:27
  • Your loop won't require an _extra_ `n` operations to "get to the end of the array to start the loop". The array elements can be accessed directly by index. That is, accessing `array[i]` is O(1). – GriffeyDog Feb 06 '14 at 21:28
  • 2
    The interviewer was probably thinking of "C strings," which are null terminated. But, no, in Java, getting the list of a string is not O(n) (same for Strings and Collections). – Jimothy Feb 06 '14 at 21:32
  • @Jimothy: Great point. I think this is the only sane explanation. – NPE Feb 06 '14 at 21:39
  • @Jimothy The question involved Strings, but I had converted it to a char array when this discussion came up. – fvrghl Feb 06 '14 at 21:43

3 Answers3

22

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

NPE
  • 486,780
  • 108
  • 951
  • 1,012
2

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.

jbaliuka
  • 249
  • 1
  • 10
0

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.

Community
  • 1
  • 1
Curtis Rutland
  • 776
  • 4
  • 12