Figuring out Big(o)

Question

for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < i*i; j++)
            {
                cout << j << endl;
                result++;
            }
        }

Running this code say for 5 it runs a total of 30 times. I know the outer loop runs N. the inner loop though is giving me some trouble since it's not n*n but i*i and I haven't seen one like this before trying to figure out T(n), and Big(O).

score 0 · Accepted Answer · edited May 23 '17 at 12:01

This algorithm is O(n^3): To realise this we have to figure out how often the inner code

cout << j << endl;
result++;

is executed. For this we need to sum up 1*1+2*2+...+n*n = n^3/3+n^2/2+n/6 which is a well known result (see e.g. Sum of the Squares of the First n Natural Numbers). Thus O(T(n)) = O(1*1+2*2+...+n*n) = O(n^3) and the (time) complexity of the algorithm is therefore O(n^3).

Edit: If you're wondering why this is sufficient (see also Example 4 in Time complexity with examples) it is helpful to rewrite your code as a single loop so we can see that the loops add a constant amount of instructions (for each run of the inner code):

int i = 0;
int j = 0;

while(i < n) {
    cout << j << endl;
    result++;
    if(j < i * i) j++; //were still in the inner loop
    else {//start the next iteration of the outer loop
        j = 0;
        i++;
    }
}

Thus the two loops 'add' the two comparisons plus the if-statement which simply makes the conditional jumps and their effects more explicit.

Figuring out Big(o)

1 Answers1