For each of the following code fragments, give an analysis of the running time (

Question

For each of the following code fragments, give an analysis of the running time (Big-Oh notation)

sum = 0;

                        for (int i = 0; i < n; 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 < n * 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; i++)

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

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

                                    sum++;

sum = 0;

                    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++;

Explanation / Answer

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

         sum++;

Find how many times each statement is executed.

for( i = 0; i < n; i++) // i = 0; executed only once: O(1)
                  // i < n; n + 1 times          O(n)
           // i++   n times          O(n)
       // total time of the loop heading:
                 // O(1) + O(n) + O(n) =        O(n)
sum = sum + i; // executed n times,                   O(n)
The loop heading plus the loop body will give: O(n) + O(n) = 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(n2).

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

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

                            sum++;

The outer loop runs n times, The nested loop runs n * n times, hence the complexity would be
O(n3)

4) 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(n2)

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

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

                            for (int j = 0; j < i * 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 runs n times, thus the overall complexity would be O(n5)

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++;

Obviously the most inner loop will run less times than in Problem 5, and a refined analysis is possible, we are usually content to neglect the if statement and consider its running time to be O(n2), yielding an overall running time of O(n5)

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.