# 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

## 1 Answer

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