Help deciphering this code and it's runtime

int[][] A = new int [n][];
for (int i=0; i<n; i++) {
    if (i % 2 == 0) // i is a multiple of 2
        A[i] = new int [n];
    else
        A[i] = new int [1];
}

for (int i=0; i<A.length; i++)
    for (int j=0; j<A[i].length; j++)
        sum = sum + A[i][j];

So I'm getting a bit confused on what the arrays are doing. The first line init开发者_如何学Cializes a 2D array with n columns. The first for loops looks at each column. If it is an even column, it will put n in the first row of that column. Now I'm a bit confused at this because it is being referenced with only one bracket even though it should be a 2D array. The same thing with the double for loops. What is the difference between A.length and A[i].length? From what I understand, the double for loops are iterating through the array and getting the sum of all the elements. Can someone clarify this because I'm a bit lost on the syntax.

Also, my instinct says that this code runs in O(n^2) time at the very least because of the double for loops. Does that seem right?

It may help you if you think of A not as a 2D array (which we commonly think of as rectangular) but as an array of arrays of ints. The outer array contains n arrays of ints, each of which may be a different size.

What A[i] = new int [n] is actually doing is placing an array of size n in the i'th element of the array A. A[i].length is the length of the array stored at position i in A.

Your instincts about O(n^2) and the nested for loops is generally correct here.

It looks like your algorithm is incomplete.

The top part initializes a 2D array such that every even top-level array element has length n and every odd top-level array element has length 1.

In the second half, the outer loop iterates over all the top-level element. There are n such elements. For each of those elements, the inner for loop sums the sub-elements. There are alternating n and 1 of those elements.

If this is Java, then by default the contents of every int[] array element will be 0. If that's true, then the final sum will be 0. And you will have spent O(n * (n/2 + n)) = O(n^2) to get that answer.