Time complexity of nested array

[poisonousgu]

    int sum=0;

    for(i1=0,i1<m,i++){
        for(i2=0,i2<m,i++){
            for(i3=0,i3<m,i++){
            ...
            ...
            ...
                for(im=0,im<m,i++){
                    sum += a[i1][i2][i3]...[im]; 
                }
            }
        }
    }

What is the time complexity of the above code?

btw, I always having problems related to time complexity, do you guys got some good article on it?
especially about the step count and loops and the growth rate of big-oh

[deceptikon]

That's an easy one because it's nothing more than a derivation of quadratic complexity. For example, if the number of dimensions, call it m is 2 then you have classic quadratic complexity: O(n^2). If m is 3 you have cubic complexity: O(n^3). Thus you generalize for any value of m by removing the constant and replacing it with a variable: O(n^m).

especially about the step count and loops and the growth rate of big-oh

Sequential stuff constitutes addition and nested stuff constitutes multiplication. So two sequential loops would not affect each other in Big-O because they're simplified into the one that has higher growth. For example:

for (int i = 0; i < n; i++) {
    ...
}

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        ...
    }
}

These two loops are additive, with the first being O(n) and the second being O(n^2). So you have precisely O(n + n^2). But Big-O removes the lower order parts because the higher order parts totally overwhelm the complexity very quickly, and thus the example above has quadratic complexity: O(n^2).

The second loop has quadratic complexity because the nested loops are defined in terms of each other. You multiply the complexity of the inner loop by the steps of the outer loop to get the total complexity. Since they're both in terms of n, it's a simple matter to say that the two loops combined have quadratic complexity.

Please see this page for details.