1)Given the two segments of code below, indicate the order of magnitude for the
ID: 3684197 • Letter: 1
Question
1)Given the two segments of code below, indicate the order of magnitude for the code. Assume that all variables have been declared properly.
a)sum = 0;
for (i1 = 0; i1 < n; i1++) {
for (i2 = 0; i2 < n; i2++) {
for (i3 = 0; i3 < n; i3++) {
sum = sum + i1+i2 +i3;
}
}
}
for (i4 = 0; i4 < n; i4++) {
for (i5 = 0; i5 < n; i5++) {
for (i6 = 0; i6 < n; i6++) {
sum = sum + i4+i5 +i6;
}
}
}
b)sum = 0;
for (i1 = 0; i1 < n; i1= 2*i1) {
for (i2 = 0; i2 < n; i2++) {
for (i3 = 0; i3 < n; i3=2*i3) {
sum = sum + i1+i2 +i3;
}
}
}
for (i4 = 0; i4 < n; i4++) {
for (i5 = 0; i5 < n; i5++) {
sum = sum + i4+i5;
}
}
Explanation / Answer
a) both segment of nested for loops go for O(n3) times (3 for loops each going upto n times and increment by 1 hence n3 times execution which is O(n3) )
hence total = O(n3)
b) first nested for loop run n/2*n*n/2 times = n3/8 which is O(n3) whereas 2nd nested for loop go for O(n2) .
Hence total = O(n3) (because we take bigger time complexity)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.