Я почти уверен, что это O (n), так как память инициализируется при выделении массива. Он не должен быть выше, чем O (n), и я не вижу способа сделать его меньше, чем O (n), так что это кажется единственным вариантом.

Чтобы уточнить, Java инициализирует массивы при распределении. Невозможно обнулить область памяти, не пройдя по ней, а размер области определяет количество инструкций. Следовательно, нижняя граница равна O (n). Кроме того, не имеет смысла использовать алгоритм обнуления медленнее, чем линейный, поскольку существует линейное решение, поэтому верхняя граница должна быть O (n). Следовательно, O (n) является единственным ответом, который имеет смысл.

Просто для забавы, однако, представьте себе странное аппаратное обеспечение, в котором ОС контролирует питание отдельных областей памяти и может обнулять область, отключив и снова включив питание. Кажется, это будет O (1). Но область может быть настолько большой, пока утилита не исчезнет (не хотелось бы потерять все), поэтому при запросе обнуления региона все равно будет O (n) с большим делителем.

Небольшой профессиональный тест на 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));


}

дал следующий результат:

big:6133612
small:6159

поэтому я предполагаю O (n). Конечно, этого недостаточно, но это намек.

Давайте просто проверим это.

class ArrayAlloc {
  static long alloc(int n) {
    long start = System.nanoTime();
    long[] var = new long[n];
    long total = System.nanoTime() - start;
    var[n/2] = 8;
    return total;
  }
  public static void main(String[] args) {
    for(int i=1; i<100000000; i+=1000000) {
      System.out.println(i + "," + alloc(i));
    }
  }
}

И результаты на моем ноутбуке Linux (i7-4600M @ 2,90 ГГц):

Таким образом, это явно выглядит O(n), но также похоже, что оно переключается на более эффективный метод с 5 миллионами элементов.