Why isn't a counter used to avoid nested for loops for index based operations?

Question

Let's assume we have a method that we want to run as fast as possible and it needs to loop on a 2D array, naturally we would do a nested for loop as such:

    int[][] arr = new int[3][3];
    for(int i = 0; i < arr.length; i++) {
        for(int j = 0; j < arr[i].length; j++) {
            arr[i][j] = j;
        }
    }

Assuming we wanted to get rid of the O(n^2), we can do something like this:

    int j = 0;
    for(int i = 0; i < arr.length; ) {
        if (j == arr[i].length - 1) {
            i++;
            if(i == arr.length) {
                break;
            }
            j = 0;
        }
        j++;
        arr[i][j] = j;
    }

Stating the obvious, it is bad to change the value of the loop counter inside of the loop body and it is less readable, but is there a scenario where this would be okay? Would this still be considered O(n^2)?

Answer 1

Both are O(N) where N is the number of elements in the array. The second one is just more confusing and has bugs.

Assuming you fix the bugs, they're both the same loop. They'll compile into similar assembly code (or Java bytecode). The second one is just more confusing (and has bugs).

So there's no good reason to write the second one.

O(n^2) isn't when you have two nested loops. O(n^2) is when the amount of time your algorithm takes is proportional to the square of the amount of input data (or more generally, the square of something). The first code runs for arr.length*arr[i].length iterations; the second code also runs for arr.length*arr[i].length iterations if you fix the bugs, it's just more confusing (and has bugs).

---

CPUs don't understand loops, only goto, and if+goto, and other basic instructions like those. Loops were one of the first shortcuts that programmers invented to make it easier to write programs. When you write

for(int j = 0; j < arr[i].length; j++) {
    arr[i][j] = j;
}

the compiler actually turns it into something like this:

j = 0;
start_of_loop:
if (j >= arr[i].length) goto end_of_loop;
arr[i][j] = j;
j++;
goto start_of_loop;
end_of_loop:

and when you write this:

    if (j == arr[i].length - 1) {
        i++;
        if(i == arr.length) {
            break;
        }
        j = 0;
    }

the compiler actually turns it into something like this:

if(j != arr[i].length - 1) goto end_of_if;
i++;
if(i == arr.length) goto end_of_loop;
j = 0;
end_of_if:

so you can see the CPU isn't going to care which way you write it - it's (approximately) the same code by the time the CPU actually runs it.

The CPU takes some time to run each instruction, so what matters is (approximately) the number of instructions it runs, and that's what we are trying to say with big-O notation: if n is twice as big, does the CPU run the same number of instructions, or a fixed amount extra, or twice as many, or 4 times as many? Big-O notation tells us that, in a useful approximate way, without caring about the exact number of instructions.

Answer 2

It’s the number of operations that counts, not the number of loops. Your code is supposed to set all array elements. Therefore if your code is correct the number of operations is proportional to the total number of array elements, no matter how you do it.

Answer 3

Both loops will turn into roughly the same thing. In Java, the former may be slightly faster because the JIT compiler may have an easier time tracking what you are doing.

From a code development perspective, readability is important. If nested for loops capture the story you need, use them because everyone can read them.

I have written code that looked like the second example. It was a case where the incrementing pattern was a lot less regular. I had an algorithm with multiple modes, labeled 0, 1, 2, 3, etc. It started in mode 0 and processed data until it came across too many errors. Then it incremented the mode, and tried again. The resulting code could have been treated as a nested pair of for loops, but the conditions for terminating the inner loop would be rather awkward, and not very for-loop-like. So instead I wrote out the if logic, as you did, to make it very clear that this was a more interesting behavior.

Its the same logic that suggests the famous C++ nugget while(*dest++ = *src++); should not be used. That little snippit copies a string from src to dest, and looks pretty snazzy while doing it. However, its terribly hard to follow because most while loop conditions don't have assignment in them, nor have multiple increment operations. For readability, its better to write that one out with a nice clear loop