# Calculate Big-O for nested for loops

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?

• 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. Apr 27, 2015 at 9:08
• @Neil Thanks, I was not very certain about the equation. Thanks again. Apr 27, 2015 at 9:10

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).
• 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. Apr 27, 2015 at 14:15