I hope you are doing well,
I am computing the Time Complexity of my algorithm which has three nested for
, but I did a trick by putting an if
in the latest for
like:
for (i=0 ; i<n1 ; i++){
for (j=0 ; j<n2 ; j++){
for (k=0 ; k<n3 ; k++){
if (A[i][j][k] == true){
...
}
}
}
}
So, if A[i][j][k]
is false
then it will be skipped and no computation time will be used.
The question that I have is that: Whether we are skipping some parts, again the complexity of the algorithm is O(n1*n2*n3)
and when n1=n2=n3=n
, is it O(n^3)
?
Thanks for your time.
If you are performing constant time operation in the if
condition:
The complexity stills remains O(n^3) because the condition and the afterthought parts of the for
loop are still getting executed.
The condition checks , i.e., i<n1
, j<n2
, and k<n3
and the increment operations such as i++
, j++
, and k++
still take place.
So, these computations are not skipped.
If you are not performing constant time operation in the if
condition:
Then time complexity will depend on the operations performed in for
loop.