Java - Give tight big-O estimates for the run times of the following code fragme

Question

Java - Give tight big-O estimates for the run times of the following code fragments.

**********PLEASE SHOW ALL OF YOUR WORK FOR THESE PROBLEMS**********

1.
public static int fragment1 (int n){
int sum = 0;
for (int i = 1; i <= n*n; i ++)
for (int j = i*i*i; j > 0 ; j --)
sum++;
return sum;
} // end fragment1

2.

public static int fragment2 (int n){
int sum = 0;
for (int i = 0; i < n*n; i +=2)
for (int j = 0; j < i; j ++)
for (int k = 0; k < j*j; k++)
sum++;
return sum;
} //end fragment2

3.

public static int fragment3 (int n){
int sum = 0;
for (int i = 1; i <= n; i *= 3)
sum++;
return sum;
} //end fragment 3

Explanation / Answer

1. It has two for loops:

Hence total running time = O(n^2*n^6) = O(n^8)

2. Here are three loops : -

Total = O(n^2*n^2*n^4) = O(n^8)

3. Here us only one loop which is runnig from 1 to n , thus O(n)

Related Questions

Navigate

• Browse (All)
• Browse J
• Subjects

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