Java : Approximate the value of sum after the following code fragment, in terms

Question

Java : Approximate the value of sum after the following code fragment, in terms of variable n in Big-Oh notation. (2 pts) [2.1] Please answer the estimated run time of the following program segment in Big-Oh notation. int sum = 0; for (int i = 1; i <= n - 3; i++) { for (int j = 1; j <= n + 4; j += 5) { sum += 2; } sum++; } for (int i = 1; i <= 100; i++) { sum++; } [2.2] Please answer the estimated run time of the following program segment in Big-Oh notation. int sum = 0; for (int i = 1; i <= n; i++) { sum++; } for (int j = 1; j <= n / 2; j++) { sum++; }

Explanation / Answer

2.1)

The run time this segment is O(N2)

Explanation:

The outer most loop runs for n-3 times and the inner runs for n+4 times.

Combining both outer and inner for loop they run O(n-3)(n+4) whose running time can be expressed as O(n2)

The second for loop runs for 100 times. Whatever the value of n be.It running can be expressed as O(1)

Therefore the running time of the this total segment can be expressed as O(n2)

The value of sum after this program segment is (n-3)((n+4)*2)+n-3+100 = 2n2-n+85 for n>3

The value of sum after this program segment is 100 for n<=3

_________________________________________________________________________________

2.2]

The running time of this programming segment is O(N)

Explanation:

The first for loop runs for n times.

The second for loop runs for n/2 times.

Combining both the for loops the running time can be expressed as O(n+n/2) i.e O(n).

Therefore the running time of this programming segment is O(N)

The value of sum after this program segment is n+n/2 for n is even

The value of sum after this program segment is n+(n-1)/2 for n is odd

Related Questions

Navigate

• Browse (All)
• Browse J
• Subjects

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