Can anyone help me identify the time plexity of the following code?

Background: this is a HackerRank algorithm problem where the editorial section lists the solution with a time plexity 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.

Can anyone help me identify the time plexity of the following code?

Background: this is a HackerRank algorithm problem where the editorial section lists the solution with a time plexity 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.

• javascript
• arrays
• algorithm
• multidimensional-array

Share Improve this question Follow asked May 21, 2020 at 23:18 bzlightbzlight 1,16055 gold badges2121 silver badges4747 bronze badges

Add a ment  | 

7 Answers 7

Sorted by: Reset to default 4

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.

The time plexity of the code is O(n) where is the length of the matrix. As you have correctly said the loop is running only once and that too equals the number of rows/ columns viz the length of the matrix. there are no nested loops. So the time plexity is definitely, O(n) for all the cases best, worst, avg.

function diagonalDifference(arr) { const size = arr.length;

let leftDiagSum = 0;
let rightDiagSum = 0;

for (let i = 0; i < size; i++) {
    leftDiagSum += arr[i][i]; // Primary diagonal
    rightDiagSum += arr[i][size - i - 1]; // Secondary diagonal
}

return Math.abs(leftDiagSum - rightDiagSum);

}

My solution:

function diagonalDifference(arr) {
let leftDiagSum = 0;
let rightDiagSum = 0;
for (let i = 0; i < arr.length; i++) {
    leftDiagSum += arr[i][i];
    rightDiagSum += arr[i][arr[i].length - (i + 1)];
}
let sum = Math.abs(leftDiagSum - rightDiagSum);
return sum;

}

You can try this also:

`

function diagonalDifference(arr) {
    let firstDiagonalSum = arr[0][0] + arr[1][1] + arr[2][2];
    let secondDiagonalSum = arr[0][2] + arr[1][1] + arr[2][0];
    let result = (secondDiagonalSum) - (firstDiagonalSum);
    
    return result;
}`

in python :

def diagonalDifference(arr):
    
    d1 = 0
    d2 = 0
    n = len(arr)

    for i in range(0, n):
        for j in range(0, n):
            
            if (i == j):
                d1 += arr[i][j]
    
            if (i == n - j - 1):
                d2 += arr[i][j]
        
    return abs(d1 - d2)

You can do this way as well

def diagonalDifference(arr):
    lr_diag = 0
    rl_diag = 0
    
    for i in range(len(arr)):
      for j in range(len(arr)):
        if i==j:
          lr_diag+=arr[i][j]
        if i==abs(j-(len(arr)-1)):
          rl_diag += arr[i][j]
    return abs(lr_diag - rl_diag)