## Issue

**Can anyone help me identify the time complexity of the following code?**

Background: this is a HackerRank algorithm problem where the editorial section lists the solution with a time complexity of O(n^2) but I think its O(n).

I believe its O(n) because we’re only using one loop to traverse the 2 dimensional array and are not using nested loops and only looping over the array once.

**Am I correct or am I missing something?**

**Solution**

```
//arr is a 2 dimensional array containing an equal number of rows and columns
function diagonalDifference(arr) {
let diff = 0;
const length = arr.length - 1;
for (let i = 0; i < arr.length; i++) {
diff += arr[i][i] - arr[i][length - i];
}
return Math.abs(diff);
}
```

**Problem**

Given a square matrix (AKA 2D Array), calculate the absolute difference between the sums of its diagonals.

For example, the square matrix ** arr** is shown below:

1 2 3

4 5 6

9 8 9

The left-to-right diagonal = 1 + 5 + 9 = 15. The right to left diagonal = 3 + 5 + 9 = 17. Their absolute difference is |15 – 17| = 2.

## Solution

Am I correct or am I missing something?

You are right, but I think their categorization of `O(n^2)`

may be due to the interpretation wherein `n`

refers to the `n`

of the input (i.e. the side-length of the matrix). In this case, the number of elements in the matrix itself is exactly `n^2`

, and thus any solution (since any solution must read in all `n^2`

inputs) is `Ω(n^2)`

(where `Ω`

roughly means “at least”).

Your categorization of the solution as `O(n)`

is correct if we say that `n`

refers to the size of the whole input matrix.

Answered By – Kevin Wang

**This Answer collected from stackoverflow, is licensed under cc by-sa 2.5 , cc by-sa 3.0 and cc by-sa 4.0 **