I need help understanding how to find the Big-Oh of a code segment

Question

My Computer Science II final is tomorrow, and I need some help understanding how to find the Big-Oh for segments of code. I've searched the internet and haven't been able to find any examples of how I need to understand it.

Here's a problem from our sample final:

for(int pass = 1; i <= n; pass++)
{
    for(int index = 0; index < n; index++) 
        for(int count = 1; count < n; count++) 
        {
            //O(1) things here.
        }
    }
}

We are supposed to find the order (Big-Oh) of the algorithm.

I think that it would be O(n^3), and here is how I came to that conclusion

for(int pass = 1; i <= n; pass++) // Evaluates n times
{
    for(int index = 0; index < n; index++) // Evaluates n * (n+1) times
        for(int count = 1; count < n; count++) // Evaluates n * n * (n) times
        {
            //O(1) things here. 
        }
    }
}
// T(n) = (n) + (n^2 + n) + n^3
// T(n) = n^3 + n^2 + 2n
// T(n) <= c*f(x)
// n^3 + n^2 + 2n <= c * (n^3)
// O(n) = n^3

I'm just not sure if I'm doing it correctly. Can someone explain how to evaluate code like this and/or confirm my answer?

Answer 1

Yes, it is O(n^3). However:

for(int pass = 1; pass <= n; pass++) // Evaluates n times
{                 //^^i should be pass

    for(int index = 0; index < n; index++) //Evaluates n times
       for(int count = 1; count < n; count++)  // Evaluates n-1 times
       {
            //O(1) things here. 
       }
    }
}

Since you have three layer of nested for loops, the nested loop will be evaluated n *n * (n-1) times, each operation inside the most inner for loop takes O(1) time, so in total you have n^3 - n^2 constant operations, which is O(n^3) in order of growth.

A good summary of how to measure order of growth in Big O notation can be found here:

Big O Notation MIT

Quoting part from the above file:

Nested loops

 for I in 1 .. N loop
    for J in 1 .. M loop
      sequence of statements
    end loop;
 end loop;

The outer loop executes N times. Every time the outer loop executes, the inner loop executes M times. As a result, the statements in the inner loop execute a total of N * M times. Thus, the complexity is O(N * M). In a common special case where the stopping condition of the inner loop is J <N instead of J <M (i.e., the inner loop also executes N times), the total complexity for the two loops is O(N^2).

Similar rationale can be applied in your case.