# Time Complexity of HackerRank Diagonal Difference

## 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.