algorithmtime-complexitybig-ocpu-time

Compute the "Time Complexity"


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.


Solution

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