是O(n)。考虑以下简单程序：

public class ArrayTest {

  public static void main(String[] args) {
     int[] var = new int[5];
  }

}

生成的字节码为：

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

}

要看的newarray指令就是指令（只需搜索newarray）。从VM规范：

从垃圾收集堆中分配一个新数组，该数组的组件类型为type且长度计数。对该新数组对象的引用arrayref被推入操作数堆栈。
新数组的每个元素都被初始化为该数组类型的默认初始值（第2.5.1节）。

由于每个元素都已初始化，因此需要O(n)时间。

编辑

查看提供的链接amit，可以在恒定时间内以默认值实现数组初始化。所以我想它最终取决于JVM。您可以进行一些粗略的基准测试，看看是否是这种情况。