Why O(n^5) time complexity?

#1 
   void function(int n) 
   { 
     int count = 0; 

     for (int i=0; i<n; i++) 
     for (int j=i; j< i*i; j++) 
         if (j%i == 0) 
         { 
            for (int k=0; k<j; k++) 
               // Print statement - O(1) operation 
          } 
    }
#2

Hey @gaganpreetsachdev1

for (int i=0; i<n; i++) --> Clearly this loop will iterate for n times

for (int j=i; j< i * i; j++)
Now in the above loop, the maximum vale of i can be (n-1). so, this loop iterates (n-1) * (n-1) times which is roughly n^2 times.

for (int k=0; k<j; k++)
The maximum value of j is roughly n^2. So roughly this loop will also run for n^2 times.

So now, the total time complexity is n * n^2 * n^2 which is O(n^5).

Hope this helps :slightly_smiling_face:
if its cleared dont forget to mark it as resolved

#3

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.