0

what's the time complexity of this program and how it is calculated. As per my understanding I think program time complexity is O(n^3).


for(int i = 0; i < n; i ++)
{
    for(int j = 0; j<n; j++)
    {
    }
        for(int k = 0; k<n; k++)
    {           
    }
}

I tried figuring out but sometimes I think n^2 and sometimes n^3.

trincot
  • 317,000
  • 35
  • 244
  • 286
Suraj Paudel
  • 27
  • 1

2 Answers2

0

It's been a while since I took Data Structures and Algorithms, but I would say that the time complexity for this code is O(n^2).

The reason for this is that the for-loop for the integer k isn't nested inside of the for-loop for the integer j. So what will happen is that you start at the outer for-loop (the one for integer i) and then you go into the for-loop for integer j. Once you've completely finished the for-loop for j, you go into the for-loop for the integer k. Once you finish the for-loop for integer k, you reiterate the for-loop for integer i.

In order for this code to have a time complexity of O(n^3), the for-loop for integer k would have to be nested inside the for-loop for integer j.

To answer your question about how to tell in general, you have to check the number of loops, and how they're placed in relation to each other - are they nested or are they sequential? I hope this is helpful.

54starr
  • 11
  • 1
0

Case 1:

for(int i = 0; i < n; i ++){
    
        for(int j = 0; j<n; j++){
        }
    
        for(int k = 0; k<n; k++){           
        }
 
 }

the complexity of the case 1 is O((n+n)*n).

case 2:

for(int i = 0; i < n; i ++){
    
        for(int j = 0; j<n; j++){
            for(int k = 0; k<n; k++){           
            }
        }    
}

The complexity of the case 2 is O(nnn)= O(n^3)

ALI.Boulerouah
  • 1
  • 2