1

I found this nested loop to calculate the Big-O notation.

for(i=0;i<n;i++)
  for(j=0;j<i*i;j++)
    for(k=0;k<j;k++)

I got the time complexity for the algorithm with this polynomial equation. Suppose C1, C2 and C3 are time constants for each loop. Please note inner loop goes to i*i.

T(n) = C1(n) + C2(n/2)(n+1) + C3(n)(n^2)(n^2+1)/2

According to this, it has the time complexity of O(n^5) Am I right on the equation?

  • 1
    possible duplicate of Big-O for nested loop – gnat Apr 27 '15 at 6:30
  • Yes, the largest term is n^5, so yes, you have growth rate O(n^5) in this case. – Neil Apr 27 '15 at 8:23
  • @gnat Inner loop goes to i*i here. So the Big-O and time complexity equation would be different. – Marlio Apr 27 '15 at 9:08
  • @Neil Thanks, I was not very certain about the equation. Thanks again. – Marlio Apr 27 '15 at 9:10
8

In this specific case, you can replace the variables with their minimum and maximum values to find the number of steps for each loop.

The first loop goes from 0 to n, the second loop goes from 0 to n*n and the inner loop goes from 0 to n*n. So there are n2 iterations of the innermost loop, times n2 iterations of the second loop, times n iterations of the outer loop. Thus your running time is O(n * n2 * n2) = O(n5).

Note that it might not always be so simple to calculate the running time. Functions that are called within the loops, recursion, loops ending early, etc. will all add to the complexity of the calculation.

  • This sounds like dubious advice. Sure, it works when the loop is simply incremented by i++ and such, but may fail in more complicated cases. – Ordous Apr 27 '15 at 14:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.