1
boolean[] arr = new boolean[n];

What is the time complexity of above initialization? Is it O(1) ir O(n)? I think it is O(1) because the program simply asks JVM for a block of memory of size n. How does JVM(hotspot) actually allocate memory in this case?

I have looked up following links so far, however the answer is not clear to me:

Thread-1 Thread-2

bp4D
  • 915
  • 12
  • 20

1 Answers1

2

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.

Eugene
  • 117,005
  • 15
  • 201
  • 306
  • Thank you, @Eugene for the writeup and link. Essentially, time complexity analysis (of data structure operation) should be aware of and account for any new array declarations when the remaining terms in polynomial are better than O(n)? – bp4D May 18 '19 at 21:01
  • 1
    It might not happen with HotSpot today, but in principle, there’s also the possibility that the JVM skips zeroing when it knows that the fresh new memory is already zeroed. E.g. some operating systems allow to request zeroed memory when allocating new memory, because they are zeroing pages anyway, for security reasons. – Holger May 20 '19 at 16:51
  • 1
    @Holger or even with `AlwaysPreTouch` may be. Good point – Eugene May 20 '19 at 17:09