Calculate Big-O for nested for loops

algorithm-analysisalgorithmsbig o

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?

Best 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.

Related Topic