For each of the following code fragments give an analysis of

For each of the following code fragments, give an analysis of the running time (Big-Oh notation). Be sure to show your work.

sum = 0;

for (int i = 0; i < n + 2; i++)

sum++;

sum = 0;

for (int i = 0; i < n; i++)

for (int j = 0; j < n; j++)

sum++;

sum = 0;

for (int i = 0; i < n; i++)

for (int j = 0; j < i; j++)

sum++;

sum = 0;

for (int i = 0; i < n*n; i++)

for (int j = 0; j < i; j++)

sum++;

sum 0;

for (int i = 0; i < n*n; i++)

for (int j = 0; j < i; j++)

for (int k = 0; k < j; k++)

sum++;

sum = 0;

for (int i = 0; i < n; i++)

for (int j = 0; j < i*i; j++)

if (j % i == 0)

for (k = 0; k < j; k++)

sum++;

Solution

1) for (int i = 0; i < n+2; i++)
         sum++;

for( i = 0; i < n+2; i++) // i = 0; executed only once: O(1)
                  // i < n; n + 2 times          O(n)
           // i++   n + 2times          O(n)
       // total time of the loop heading:
                 // O(1) + O(n+2) + O(n+2) =        O(n+2)
sum = sum + i; // executed n times,                   O(n)
The loop heading plus the loop body will give: O(n+2) + O(n+2) = O(n).
Loop running time is: O(n).

2) for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            sum++;

Applying Rule 1 for the nested loop (the \'j\' loop) we get O(n) for the body of the outer loop.
The outer loop runs n times, therefore the total time for the nested loops will be
O(n) * O(n) = O(n*n) = O(n²).

3) for (int i = 0; i < n; i++)
    for (int j = 0; j < i; j++)
        sum++;

The running time for the operation sum++ is a constant.
The outer loop runs n times. For the first execution of the outer loop the inner loop runs only once. For the second execution of the outer loop the inner loop runce twice, for the third execution - three times, etc. Thus the inner loop will be executed 1 + 2 + ... + (n-1) + n times.

1 + 2 + ... + (n-1) + n = n(n+1) / 2, which gives (n+1) / 2 on average.

Thus the total running time would be O(n*(n+1)/2) = O(n*n) = O(n²)

In general, when the upper bound of the loop variable depends on some other variable, we consider the largest value of the bound.

4)
sum = 0;
for (int i = 0; i < n*n; i++)
    for (int j = 0; j < i; j++)
        sum++;

The running time for the operation sum++ is a constant.
The most inner loop runs at most n*n times, and the outer loop runs n*n times, thus the overall complexity would be O(n⁴)

5)
sum 0;
for (int i = 0; i < n*n; i++)
    for (int j = 0; j < i; j++)
        for (int k = 0; k < j; k++)
            sum++;

The running time for the operation sum++ is a constant.
The most inner loop runs at most n*n times, the middle loop also runs at most n*n times, and the outer loop also runs n*n times, thus the overall complexity would be O(n⁶)

6) for (int i = 1; i < n; i++)
    for (int j = 1; j < i * i; j++)
        if (j % i == 0)
            for (k = 0; k < j; k++)
                sum++;

The running time for the operation sum++ is a constant.
The most inner loop runs at most n*n times, the middle loop also runs at most n*n times, and the outer loop runs n times, thus the overall complexity would be O(n⁵)