Is there any difference in time complexities of declaring, instantiating and initializing an array in the following methods in JAVA?

Question

I am following an online course about data structures and algorithms. In that course, the instructor tells that the time complexities of following ways are different.

Method 1:

 Declare:

                int arr[]------------>O(1)

 Instantiation:

                arr = new int[size]------>O(1)


 Initialization:
               arr[0]=0;------------>O(1)
                                     -------------->O(n)
               arr[1]=1;------------>O(1)

Method 2:

 Declaration,instantiation and initialization:

               int arr[]={10,20,30}---------------->O(1)

I need to know that by following the second method can we optimise our program and how can it possible to tell that it's having O(1) ,what's the difference between both these methods.

I mean that I think although the second method is having fewer steps it internally follows all the steps which are in the first method, so it can't be O(1) it's also O(n) , Iam I correct?

Answer 1

Java’s array initializer syntax is just syntactic sugar for the instructions of allocating an array and assigning a value to each element.

This can be easily verified by the following code:

import java.io.IOException;
import java.nio.file.Paths;

public class ArrayInitializer {
    public void form1() {
        int arr[] = new int[3];
        arr[0] = 10;
        arr[1] = 20;
        arr[2] = 30;
    }

    public void form2() {
      int arr[] = { 10, 20, 30 };
    }

    public static void main(String[] args) throws Exception {
        decompile();
    }

    private static void decompile() throws InterruptedException, IOException
    {
      new ProcessBuilder(Paths.get(System.getProperty("java.home"))
          .getParent().resolve(Paths.get("bin", "javap")).normalize().toString(),
          "-c", "-cp", System.getProperty("java.class.path"),
          ArrayInitializer.class.getName())
      .inheritIO()
      .start().waitFor();
    }

    private ArrayInitializer() {}
}

which prints

Compiled from "ArrayInitializer.java"
public class ArrayInitializer {
  public void form1();
    Code:
       0: iconst_3
       1: newarray       int
       3: astore_1
       4: aload_1
       5: iconst_0
       6: bipush        10
       8: iastore
       9: aload_1
      10: iconst_1
      11: bipush        20
      13: iastore
      14: aload_1
      15: iconst_2
      16: bipush        30
      18: iastore
      19: return

  public void form2();
    Code:
       0: iconst_3
       1: newarray       int
       3: dup
       4: iconst_0
       5: bipush        10
       7: iastore
       8: dup
       9: iconst_1
      10: bipush        20
      12: iastore
      13: dup
      14: iconst_2
      15: bipush        30
      17: iastore
      18: astore_1
      19: return

  public static void main(java.lang.String[])  throws java.lang.Exception;
    Code:
       0: invokestatic  #22                 // Method decompile:()V
       3: return
}

So, if the compiled code does not differ, there can’t be a performance difference caused by the form of the source code.

This doesn’t preclude runtime optimizations made by the JVM, e.g. when it detects that this is an allocation followed by filling with values whose evaluation can not fail in a way that would leak an uninitialized array. But these optimizations would apply in either case, as the source code form doesn’t matter.

A practical example is discussed in this article regarding the toArray method of collections, whose performance turns out to be dependent on the JVM’s ability to recognize an array allocation which is immediately followed by a copy operation overwriting the entire created array.

Answer 2

It is possible to initialize an array in constant time. I do not know which, if any, JVM implementation do it, but it is possible. Since this technique requires 3 times as much memory, it may very well not be used by any JVM implementation.

Assuming the JVM do not use this technique, then

arr = new int[size]

and

int arr[]={10,20,30}

will both run in O (n) (in the first case, all element in the array need to be zeroed).

But in case this (or a similar technique) is used, your instructor is correct.

Edit

Without fancy initialization technique, the complexity is O (n) in both case. But the constant factor is probably different. So I did a benchmark using jmh with 100 sized arrays (sorry, I was to lazy to write longer arrays). The result is below:

# Run complete. Total time: 00:20:13

Benchmark                                  Mode  Cnt         Score       Error  Units
ArrayInitBenchmark.initialize_and_set     thrpt  200  32341391,483 ± 46429,821  ops/s
ArrayInitBenchmark.initialize_only        thrpt  200  32523162,079 ± 34682,391  ops/s
ArrayInitBenchmark.initialize_with_zeros  thrpt  200  36267571,539 ± 34839,701  ops/s

• initialize_and_set is the OP’s first method.
• initialize_only is the OP’s second method.
• initialize_with_zeros is a mere new int[size].

As you can see, the second method is a bit faster, but less than 1% faster than the first one (32.3 M ops/s vs 32.5 M ops/s). That is, on my machine, with oracle JDK 1.8.0_201. (testing with Java 13 would have required me to setup a new jmh project, while I had everything already setup for Java 8).