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.

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