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

by

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.

More Related Contents:

  1. Does Java JIT compiler sacrifice performance to favor Collections?
  2. Array or List in Java. Which is faster?
  3. boolean[] vs. BitSet: Which is more efficient?
  4. What is more efficient: System.arraycopy or Arrays.copyOf?
  5. Hashmap vs Array performance
  6. What's the output of this code written in java?
  7. how to replace display array list equals another array list values
  8. java.lang.arrayoutofboundexception length:10 index:10
  9. How do i format a ArrayList for printing?
  10. Convert ArrayList to String[] array [duplicate]
  11. .toArray(new MyClass[0]) or .toArray(new MyClass[myList.size()])?
  12. Swing animation running extremely slow
  13. Cannot create an array of LinkedLists in Java…?
  14. How to convert an int array to String with toString method in Java [duplicate]
  15. How to find the index of an element in an array in Java?
  16. Variable length (Dynamic) Arrays in Java
  17. How to display a svg byte array as an image in a JasperReport?
  18. ArrayIndexOutOfBoundsException when iterating through all the elements of an array
  19. PDF to byte array and vice versa
  20. Use of array of zero length
  21. What is the time complexity of HashMap.containsKey() in java?
  22. Most efficient Java primitive collections library [closed]
  23. Creating nested JSON object for the following structure in Java using JSONObject? [closed]
  24. Why is array indexing in Java start with 0?
  25. How to see if an object is an array without using reflection?
  26. Generate Random Numbers in Array [duplicate]
  27. How to remove last comma and space in array? Java [duplicate]
  28. What GC parameters is a JVM running with?
  29. Finding the median value of an array?
  30. Java: Checking equality of arrays (order doesn’t matter)

Leave a Comment