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

### The Scenario

### What I know

### What I don't know

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

Sum all of the values in all of the arrays.

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],
]
```

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?

Solution

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.

- How to generate uniformly distributed subintervals of an interval?
- Generating random number in a non-power-of-2 range from random bits
- Algorithm - Search and Replace a string
- Looking for a branchless algorithm for converting a specific set of 4-bit integers
- Different results for XIRR between Excel and ExcelFinancialFunctions 3.2.0
- Find four,whose sum equals to target
- A* algorithm can't find the goal in Python
- Efficiently getting all divisors of a given number
- Are there any existed API to split IEnumerable<T> to many Vector<T> in CSharp？
- Generating all divisors of a number given its prime factorization
- Efficient way to insert a number into a sorted array of numbers?
- BFS Maximize Minimum Distance from a Monster along a path
- Is there effective algorithm that will return all different combination?
- Big O of algorithm that steps over array recursively
- Modification of Dijkstra's algorithm to make it work with negative weights and its time complexity
- Traversing/Moving over an unfolded cube
- Fibonacci Recursion using Golden Ratio(Golden Number)
- Karatsuba implementation in C
- Why is O(n) better than O( nlog(n) )?
- What is Sliding Window Algorithm? Examples?
- How to write a function to navigate through a non-binary tree?
- Evenly distribute QDate values into certain number of slots
- Find max product using divide and conqure in O(n) time
- Cache-friendly sqare matrix transposition logic issue
- Why doesn't Dijkstra's algorithm work for negative weight edges?
- Fast Convertion From Adjacency List to Edge List
- I convert ASCII words into numbers but am stuck trying to decode them. How to convert 1=a, 2=b, 28=ab etc? (psudeocode okay)
- Reversing the word order in a string in place
- Trying to make a 2x2 rubik's cube solving algorithm , how do i find the solution path (DFS)?
- question about missing element in array