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

tucuxi 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);