Java: 1.2 Approximate the run-time of the following code fragments, in terms of
ID: 642117 • Letter: J
Question
Java:
1.2 Approximate the run-time of the following code fragments, in terms of n:
a) int sum = 0;
for (int j = 1; j < n; j++){
sum++;
if (j % 2 == 0){
sum++;
}
}
b) int sum = 0;
for (int i = 1; i <= n * 2; i++){
for (int j = 1; j <= n; j++){
sum++;
}
}
for (int j = 1; j < 100; j++){
sum++;
sum++:
}
c) int sum = 0;
for (int i = 1; i <= n; i++){
for( int j = 1; j <= 1000000; j++){
sum += 10;
}
}
Sum += 9999;
Explanation / Answer
Order of a program is in general the number of times the loop runs.
a) order = O(n) loop j runs for n times
b) order = O(n2Xn) + O(100) total loop iteration is n3
= O(n3) +O(100)
= O(n3) if n is large
c) order = O(nX1000000)
= O(1000000n)
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.