Search code examples
cfor-loopbig-onotation

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

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?

Solution

  • 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).