Big O Notation - How do you describe a 2D array of different lengths?

Question

I'm having trouble understanding what the Big O notation would be for nested data structures like 2D arrays or an object of arrays.

The Scenario

Sum all of the values in all of the arrays.

What I know

For example, my understanding is the below data structure would be O(n^2) since both dimensions are the same length (3x3).

// O(n^2)

const arr = [
  [1,2,3],
  [1,2,3],
  [1,2,3],
]

This would be O(n * m) where n is the length of the first dimension (2), and m is the length of the second dimension (3).

// O(n * m)

const arr = [
  [1,2,3],
  [1,2,3],
]

What I don't know

But what about a data structure where the second dimension arrays are different lengths?

// Maybe O(n * m)?

const arr = [
  [1,2,3],
  [1,2,3,4,5,6],
  [1,2]
]

let sum = 0

for (let nums of arr) {
  for (let num of nums) {
    arrSum += num
  }
}

// sum = 30

Or an object where the values are arrays?

// Maybe O(n * m)?

const obj = {
  a: [1,2,3],
  b: [1,2,3,4,5,6],
  c: [1,2]
}

let sum = 0

for (let nums of Object.values(obj)) {
  for (let num of nums) {
    sum += num
  }
}

// sum = 30

I am getting stumped on how this would be represented in Big O notation. My thought is you would still go with O(n * m) where n is the length of the first dimension (or the number keys), and m represents the longest array in the second dimension (or key value).

Am I thinking about this correctly?

Answer 1

No need to make this more complicated than it is. n and m are both simply variables. What they describe is entirely up to you. Actually a proper choice for what you base the runtime-complexity of your algorithm on can be of considerable importance.

So for the case of an array of arrays with different lengths, you can simply pick n as the sum of the length of all "inner" arrays. For the case with the object, the problem can be reduced to the first problem. Minor nitpick: you depend on the internal behavior of Object.values; I've simply assumed it's in O(n).

So in general: pick the most accurate description of the problem-size, not the structure. Whether you're summing all elements of an 256 x 256 or an 2 x 32768 array won't make any difference in terms of runtime-complexity.