algorithmtime-complexitybig-o

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

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

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