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