Java: What's the Big-O Time of Declaring an Array of Size N

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

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.

Is Array declaration linear time operation or constant time operation?

I think that in general it is O(n), since the declared array need to be zeroes with default values, in your case with false.

But a VM can also prove that this array is not read immediately, that is someone first writes all the elements to it and only after that, reads them. In such a condition the complexity would be O(1), because you are not really doing anything (no default values are placed inside the array itself) - thus constant.

This, for example, is what happens in java-11 with Collection::toArray sort of, via :

default <T> T[] toArray(IntFunction<T[]> generator) {
    return toArray(generator.apply(0));
} 

So when you have something like:

List.of(1, 2, 3, 4)
    .toArray(x -> new Integer[x]);

The implementation will actually do new Integer[0] and use that coupled with some System.arrayCopy, instead of the inferred new Integer[4]. This is done because the VM can prove that zeroing is not needed, thus skip it entirely.

What is the time complexity of assigning multiple elements to the array using the notation that uses only a single code line?

Very related, so check it out: Java: what's the big-O time of declaring an array of size n?

The resulting bytecode for initializing an array involves the newarray instruction, which is O(n) as each element is initialized to the default state before anything else. See: JVM Spec., page 576:

[...] Each of the elements of the new array is initialized to the defaultinitial value (§2.3, §2.4) for the element type of the array type.

What you are using here additionally is an array initializer, so let's check out the bytecode:

public class Main {
    public static void main(String[] args) {
        int[] array = {1, 2 , 3, 4, 5};
    }
}

... is compiled to ...

public class Main {
  public Main();
    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: dup
       4: iconst_0
       5: iconst_1
       6: iastore
       7: dup
       8: iconst_1
       9: iconst_2
      10: iastore
      11: dup
      12: iconst_2
      13: iconst_3
      14: iastore
      15: dup
      16: iconst_3
      17: iconst_4
      18: iastore
      19: dup
      20: iconst_4
      21: iconst_5
      22: iastore
      23: astore_1
      24: return
}

Notice the newarray with iconst_5 passed to it. This belongs to the "new int[5] part" of the code, where iconst_5 is just 5 ("integer constant 5"). Ignore the dup and astore_1, they're not so important for the question.

Notice the iconst_0, iconst_1 and iastore block, which is repeated for other integer constants. iastore is the instruction to store a value in an array, where the first parameter is the index and the second parameter is the value. Two lines before the iastore are the arguments. So what you see is that the bytecode reads each of the elements in your array initializer and stores it in the array.

So what the one-liner does is actually very similar (or equivalent) to this:

public class Main {
    public static void main(String[] args) {
        int[] array = new int[5];
        array[0] = 1;
        array[1] = 2;
        array[2] = 3;
        array[3] = 4;
        array[4] = 5;
    }
}

As you can see, the one-liner you've shown is actually 2 * O(n) at bytecode-level.

Time Complexity of Memory Allocation for an Array (not dynamic)

In java, when you create a new array of int, all members of the array must get the initial value for int (which is '0'), so the initialization includes n assignments of the value 0, thus taking O(n).

You can also verify it, using the following code, with different n's:

public static void main(String[] args)
{
    int n = 1000000;
    int numSamples = 10000;
    long sumTime = 0;
    for (int i = 0; i < numSamples; i++)
    {
        sumTime += test(n);
    }
    double average = sumTime / (double) numSamples;
    System.out.println(average);
}

private static long test(int size)
{
    long start = System.currentTimeMillis();
    int[] a = new int[size];
    return System.currentTimeMillis() - start;
}

What is the time complexity of declaring a 2d array

It depends on what you mean by n.

Some may define n as your i and see the j depended to that, for example a square n * n, for that definition you get O(n^2), O(i * i) or O(i * j) if j in O(i).

However you defined it as n = i * j. So yes, it is O(n) for your definition of n but that notation hides O(i * j) which may be more appropriate.

---

However note that it depends on whether your language actually initializes all those array entries at creation. Some languages don't do that!

I guess your code is Java, this language actually sets every entry to an initial value. In your case this would be null, thus it indeed creates i * j elements and sets them to null, yielding O(i * j).

Also take a look at Syntax for creating a two-dimensional array, which explains in detail how your code works.

Space Complexity of an array?

Complexity is only relevant when you try to foresee the performances of your algorithm with various input. I don't think it has any meaning to just speak about the space-complexity of an array without any context.

If you'll always create an array of size N (hard-coded), it's O(1), because no matter what input your algorithm crunches, the space taken by your array is the same.

If your N grows with the size of the input, it's O(f(n)), where f(n) is the relation between n (size of input) and N (size of array).

NOTE : the formulation O(...) is a mathematical symbol to represent magnitude without any regard to the multiplier (sorry for the lack of precision, I'm way over my math degree and never learned the english terms), so, if N is a constant, O(N) = O(1) (they have the exact same meaning).

And if I'm remembering it right, if f < C * g , O(f) = O(g). Thus, if N is < 200 , O(N) = O(200) = O(1)

---

Related Topics