i = 1; C1 while(i <= n) { C2 j = 1; C3 while(j <= n){ C4 System.out.print(j); C5
ID: 3670577 • Letter: I
Question
i = 1;
C1
while(i <= n) {
C2
j = 1;
C3
while(j <= n){
C4
System.out.print(j);
C5
j = j*2; //ßnote this
C6
}
i = i+1;
C8
}
T(n)=
So, the growth-rate function for this algorithm is O( )
[0.35 pts]
Operations
Times
sum = 0;
C1
n = 10;
C2
for (int i = 0; i < n; i++)
C3
for (int j = 0; j < n; j++)
C4
for (int k = 0; k < n; j*2)
C5
{
sum = i+j+k;
C6
System.out.print(sum);
C7
}
T(n)=
So, the growth-rate function for this algorithm is O( )
Operations
Times
sum = 0
C1
for(int i = 0; i < n; i++)
C2
for(int j = 0; j<2*n; j++)
C3
sum += i * j ;
C4
T(n) =
So, the growth-rate function for this algorithm is O( )
Explanation / Answer
i = 1; // C1
while(i <= n) { // C2
j = 1; // C3
while(j <= n){ // C4
System.out.print(j); // C5
j = j*2; //ßnote this C6
}
i = i+1; // C8
}
T(n) = C1 + n * (C2 + C3 + lg n * (C4 + C5 + C6) + C8)
T(n) = C1 + n * (C2 + C3 + C8) + n * lg 2 * (C4 + C5 + C6)
So, the growth-rate function for this algorithm is O(nlg n)
---------------------------------------------------------------
sum = 0; // C1
n = 10; // C2
for (int i = 0; i < n; i++) // C3
for (int j = 0; j < n; j++) // C4
for (int k = 0; k < n; k*2) // C5 Edited j*2 to k*2 else otherwise the loop will be infinite.
{
sum = i+j+k; // C6
System.out.print(sum); // C7
}
T(n) = C1 + C2 + n * (C3 + n * (C4 + lg n *(C5 + C6 + C7) ) )
T(n) = C1 + C2 + n * C3 + n2 * C4 + n2 * lg n *(C5 + C6 + C7)
So, the growth-rate function for this algorithm is O(n2lg n)
-----------------------------------------------------------------
sum = 0 // C1
for(int i = 0; i < n; i++) // C2
for(int j = 0; j<2*n; j++) // C3
sum += i * j ; // C4
T(n) = C1 + n * ( C2 + 2*n ( C3 + C4))
T(n) = C1 + n * C2 + 2*n2 ( C3 + C4)
So, the growth-rate function for this algorithm is O(n2)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.