Struggling to understand how two nested for-loops can still have O(n) runtime

Question

I have the following piece of solution code to rotate an image to the right.

It first transposes the matrix and then flips it on the vertical axis:

public static void rotateSquareImageCW(int[][] matrix) {
    transposeMatrix(matrix);
    flipVerticalAxis(matrix);
}   


public static void transposeMatrix(int[][] matrix) {
    int n = matrix.length - 1;
    int temp = 0;
    for(int i = 0; i <= n; i++){
        for(int j = i+1; j <= n; j++){
            temp = matrix[i][j];
            matrix[i][j] = matrix[j][i];
            matrix[j][i] = temp;
        }
    }
}


private static void flipVerticalAxis(int[][] matrix) {
    int n = matrix.length - 1;
    int temp = 0;
    for(int i = 0; i <= n; i++){
        for(int j = 0; j <= n/2; j++){
            temp = matrix[i][j];
            matrix[i][j] = matrix[i][n-j];
            matrix[i][n-j] = temp;
        }
    }
}

The code author (Firecode.io) says that this code runs in O(n) space and O(1) time.

However, we can see that the "transposeMatrix" and "flipVerticalAxis" functions have nested for-loops that iterate upon the rows/columns of the matrix.

Shouldn't this be O(N^2), dependent upon the size of the columns and rows?

How is this still O(N)? Can anyone explain or rationalize this?

Answer 1

As already pointed out in the comments, it depends on the definition of n in the O(n) expression.

The most plausible definition is that n is to denote the width or height of the matrix. This is in line with various matrix algorithm analyses, and additionally supported by the fact that the code uses a variable named n with exactly that meaning.

The code uses only a fixed set of additional storage elements, being i, j, n and temp, so it's constant space (not counting the pre-existing matrix), meaning O(1) space complexity.

The two nested loops each iterate over n (or n/2) elements, so you're absolutely right, that means O(n²).

So, it's O(1) space and O(n²) time complexity.