Java: what's the big-O time of declaring an array of size n?

Question

What is the running time of declaring an array of size n in Java? I suppose this would depend on whether the memory is zero'ed out on garbage collection (in which case it could be O(1) ) or on initialization (in which case it'd have to be O(n) ).

Answer 1

It's O(n). Consider this simple program:

public class ArrayTest {    public static void main(String[] args) {      int[] var = new int[5];   }  } 

The bytecode generated is:

Compiled from "ArrayTest.java" public class ArrayTest extends java.lang.Object{ public ArrayTest();   Code:    0:   aload_0    1:   invokespecial   #1; //Method java/lang/Object."<init>":()V    4:   return  public static void main(java.lang.String[]);   Code:    0:   iconst_5    1:   newarray int    3:   astore_1    4:   return  } 

The instruction to take a look at is the newarray instruction (just search for newarray). From the VM Spec:

A new array whose components are of type atype and of length count is allocated from the garbage-collected heap. A reference arrayref to this new array object is pushed into the operand stack. Each of the elements of the new array is initialized to the default initial value for the type of the array (§2.5.1).

Since each element is being initialized, it would take O(n) time.

EDIT

Looking at the link amit provided, it is possible to implement array-initialization with a default value, in constant time. So I guess it ultimately depends on the JVM. You could do some rough benchmarking to see if this is the case.

Answer 2

A small none professional benchmark on JRE1.6:

public static void main(String[] args) {     long start = System.nanoTime();     int[] x = new int[50];     long smallArray = System.nanoTime();     int[] m = new int[1000000];     long bigArray = System.nanoTime();     System.out.println("big:" +  new Long( bigArray - smallArray));     System.out.println("small:" +  new Long( smallArray - start));   } 

gave the following result:

big:6133612 small:6159 

so I assume O(n). of course, it is not enough to be sure, but it's a hint.