if i do this
int n = some arbitrary number
int[] array = new int[n];
is the time needed linear (O(n)) or constant (O(1))?
i looked in the javadocs and eg. here in StackOverflow but didn't find an answer because all the posts i saw deal with dynamic allocation.
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;
}
