1

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.

Community
  • 1
  • 1
Fynn
  • 303
  • 1
  • 11
  • 1
    you may check this link http://stackoverflow.com/questions/5640850/java-whats-the-big-o-time-of-declaring-an-array-of-size-n – Razib Jun 27 '16 at 10:30
  • i just didn't find it before ... should i delete the question (its a duplicate after all) – Fynn Jun 27 '16 at 10:36

1 Answers1

1

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;
}
Yoav Gur
  • 1,366
  • 9
  • 15