Why is this code considered O(N^6) in Big Oh notation?

Question

I was just reading another question and this code intrigued me:

for(i = 0; i < n; i++)
{
    for(j = 0; j < i*i; j++)
    {
        for(k = 0; k < i*j; k++)
        {
            pseudo_inner_count++;
            for(l = 0; l < 10; l++);
        }
    }
}

I don't understand how this can be O(N^6). Can someone break it down for me?

Answer 1

Actually it is:

• The i loop iterates O(N) times, so the value of i is O(N), so we can say O(I)=O(N).
• The j loop iterates O(I^2) = O(N^2) times (when considered on its own, without the outer loop).
• The k loop iterates O(I*J) = O(N*N^2) = O(N^3) times.
• The l loop just iterates 10 times so that is O(1).

The loops are nested so we have to multiply these together (do you understand why?). The total is O(N)*O(N^2)*O(N^3) = O(N^6).

Answer 2

It's

n for the first loop n² for the second loop n³ for the third loop

The inner loop is O(1)

The total is O(n⁶).

The reason the third loop is n³ is because when you think about it j reaches n² and i reaches n, so i*j reaches n³.