Need help understanding Big-O

Question

I'm in a Data Structures class now, and we're covering Big-O as a means of algorithm analysis. Unfortunately after many hours of study, I'm still somewhat confused. I understand what Big-O is, and several good code examples I found online make sense. However I have a homework question I don't understand. Any explanation of the following would be greatly appreciated.

Determine how many times the output statement is executed in each of the following fragments (give a number in terms of n). Then indicate whether the algorithm is O(n) or O(n2):

    for (int i = 0; i < n; i++)
        for (int j = 0; j < i; j++)
            if (j % i == 0)
                System.out.println(i + ” ” + j);

Answer 1

Suppose n = 5. Then, the values of i would be 0, 1, 2, 3, and 4. This means that means that the inner loop will iterate 1, 2, 3, 4, and 5 times, respectively. Because of this, the total number of times that the if comparison will execute is 1+2+3+4+5. A mathematical formula for the sum of integers from 1 to n is n*(n+1)/2. Expanded, this gives us n^2 / 2 + n / 2.
Therefore, the algorithm itself is O(n^2).

For the number of times that something is printed, we need to look at the times that j%i=0. When j < i, the only time that this can be true is when j = 0, so this is the number of times that j = 0 and i is not 0. This means that it is only true once in each iteration of the outer loop, except the first iteration (when i = 0). Therefore, System.out.println is called n-1 times.

Answer 2

A simple way to look at it is :

A single loop has a complexity of O(n)

A loop within a loop has a complexity of O(n^2) and so on.

So the above loop has a complexity of O(n^2)

Answer 3

This function appears to execute in Quadratic Time - O(n^2).

Here's a trick for something like this. For each nested for loop add one to the exponent for n. If there was three loops this algorithm would run in cubic time O(n^3). If there is only one loop (no halving involved) then it would be linear O(n). If the array was halved each time (recursively or iteratively) it would be considered logarithmic time O(log n) -> base 2.

Hope that helps.