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


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, 2015 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, 2015 at 8:23
  • @gnat Inner loop goes to i*i here. So the Big-O and time complexity equation would be different.
    – malintha
    Apr 27, 2015 at 9:08
  • @Neil Thanks, I was not very certain about the equation. Thanks again.
    – malintha
    Apr 27, 2015 at 9:10

1 Answer 1


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, 2015 at 14:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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