What is the exact time complexity of this algorithm?

Question

I attempted to solve the problem at this HackerRank link (https://www.hackerrank.com/challenges/diagonal-difference/problem?isFullScreen=true) Given a square matrix, calculate the absolute difference between the sums of its diagonals., But I wanted to avoid implementing the ( O(n^2) ) algorithm. Instead, I devised the version below. However, I'm curious about its complexity; it appears to be ( O(n) ), but due to the final condition where i is incremented only when j traverses the columns, it might actually be closer to ( O(n^2) ). Could someone please help me understand this?

function diagonalDifference(arr = [[]]) {
  let i = 0;
  let j = 0;
  let mainDiagonal = 0;
  let secondDiagonal = 0;

  const rows = arr[0].length;

  while (i < rows) {
    if (i === j) {
      mainDiagonal += arr[i][j];
    }

    if (j + i === rows - 1) {
      secondDiagonal += arr[i][j];
    }

    if (j === rows - 1) {
      j = 0;
      i++;
    } else {
      j++;
    }
  }

  return Math.abs(mainDiagonal - secondDiagonal);
}

I asked ChatGPT, which indicated the complexity as ( O(n) ), while Codeium suggested ( O(n^2) ).

Answer 1

The complexity is O(n^2).

The code although has only one outer loop the conditions are written such that there is an operation on every matrix cell. Every time you are reaching the end of one row (by visiting all its cells column by column), then you move to the next row.

You are basically doing an interaction of every column of every row. So if there are 6 rows and columns, you will have 36 operations. Hence O(n^2).

Before looking at the code, visualize what the you tried to do with the code and you will be able to answer yourself better.