# Algorithm complexity of traversing a 3D array

Asked by At

I have an algorithm that traverses a 3d array. For every value in the array I do some compiutations. I'm trying to figure out the time-complexity of the algorithm. In my case, it's not a complete traverse, some value of the array are not considered.

``````def process_matrix(k: int, V: int):
import numpy as np
sp_matrix = np.zeros((V, V, k))

for e in range(k):
for i in range(V):
# Note that the range of index j decreases while index i is growing
for j in range(i, V):
# Also the index a decreases acording to index i
for a in range(i, V):

if (something):
sp_matrix[i][j][e] = set_some_value()
``````

As you can see I'm not considering the values j < i for every index e. If we take only the three most outer loops, I think the complexity is:

V * (1+V)/2 * k

k -> the most outer loop

V*(1+V)/2 -> for the sencond and third loop I used Gauss formula for adding consecutive numbers

With some approximation, the complexity for this three loops, I think is O(((V^2)/2)*k).

First I thought the inner loop contributes to the O with another (1+V)/2. With the result (V * (1+V)/2 * k) * (1+V)/2. But then I considered this situation:
k = 1
V = 3
The resulting array is:

```        j=0  j=1  j=2
i=0 | 3 | 3 | 3 |
i=1 | x | 2 | 2 |
i=2 | x | x | 1 |
(the values in the matrix rapresents how many times the most inner loop.. loops)

```

The total is: 3+3+3+2+2+1 = 14
I expect the same value using my formula (V * (1+V)/2 * k) * (1+V)/2,
(3*(1+3)/2*1) * (1+3)/2 = 12
But it's not...

## 1 Answers On Best Solutions

Big-O notation is about setting upper limits, ignoring constant factors. In this sense, and considering the 3 outer loops, `O(((V^2)/2)*k) = O(k * V^2)`, and if `k` is constant, `= O(V^2)`.

However, if you start to count executions of the innermost code, and compare those against your expected number of executions, you are leaving big-O territory, since constant factors can no longer be ignored. Also, counting executions of a single instruction, while useful, is by no means as exact as measuring real-world performance (which, however, will depend on the exact workload and machine/environment you test it on).

Since your 3 inner loops are essentially drawing a tetrahedron, you can use its formula to get an approximation of complexity: O(V^3 / 3). But, if you want to get exact, I have successfully tested out the following JS code:

``````let K=1, V=6, t=0;  // t is for counting totals; reset to 0 for each try
for (let k=0; k<K; k++)               // inside repeats K times
for (let i=0; i<V; i++)           // inside repeats V*K times
for (let j=i; j<V; j++)       // inside repeats (V+1)*(V) / 2 * K times
for (let a=i; a<V; a++)   // inside repeats (V+1)*(V+.5)* V / 3 * K times
console.log(k,i,j,a,++t, (V+1)*(V+.5)* V / 3 * K); ``````