For each sample of code given below, indicate precisely how many times each line

Question

For each sample of code given below, indicate precisely how many times each line runs in terms of the variables given. Sometimes, you will be able to give an exact integral answer, like "10". Other times, your answer will be in terms of n or some other variable or combination of variables. If the snippet of code is a method, you do not have to write the number of times the top line (the method declaration itself) is executed.

Q1(a)

double sum_triples(double array[], int n) {

//n: size of the array. Assume n is divisible by 3

double sum=0;

for (int i=0; i<n; i=i+3)

sum = sum + array[ i ];

return sum;

}

(b)

double sum_exponentials(int n) {

//n is a power of 2, i.e., n=2^k or k=log2(n)

int sum=0;

for (int i=1; i<n; i=i*2)

sum = sum + i;

return sum;

}

(c)

for (int i=0; i<10; i++)

for (int j=0; j<n; j++)

cout << i << “,” << j << endl;

(d)

for (int i=0; i<n; i++)

for (int j=0; j<n; j++)

cout << i << “,” << j << endl;

(e)

for (int i=0; i<n; i++) //assume n is divisible by 2

for (j=n/2; j>i; j--)

sum = i+j;

(f)

double sum_matrix( double matrix[][], int m, int n ) {

//m: num of rows; n: num of cols

double sum=0;

for (int i=m-1; i>=0; i--) {

for ( int j=n-1; j>=0; j--) {

sum = sum + matrix[ i ][ j ];

}

}

return sum;

}

Explanation / Answer

Q1(a)
double sum_triples(double array[], int n) {
//n: size of the array. Assume n is divisible by 3

double sum=0; ---------------------> 1 time
for (int i=0; i<n; i=i+3) ------------> n/3 +1 times (extra last condition)
sum = sum + array[ i ]; ------------> n/3 times
  
return sum; ------------------------> 1 time
}

(b)
double sum_exponentials(int n) {
//n is a power of 2, i.e., n=2^k or k=log2(n)

int sum=0; ---------------------> 1 time
for (int i=1; i<n; i=i*2) ---------> n/2 + 1 times
sum = sum + i; ------------------> n/2 times

return sum; -----------------------> 1 time
}
(c)
for (int i=0; i<10; i++) ------> 11 times
for (int j=0; j<n; j++) ------------> n+1 times
cout << i << “,” << j << endl; ---> 11xn times
(d)
for (int i=0; i<n; i++) ----------------> n+1 times
for (int j=0; j<n; j++) ---------------> n+1 times
cout << i << “,” << j << endl; -------> n^2 times
(e)
for (int i=0; i<n; i++) //assume n is divisible by 2 ---------------> n+1 times
for (j=n/2; j>i; j--) --------------> n/2 + 1 time
sum = i+j; ------> n(n/2) times
(f)
double sum_matrix( double matrix[][], int m, int n ) {
//m: num of rows; n: num of cols

double sum=0; ----------------> 1 time
for (int i=m-1; i>=0; i--) { -----------> m+1 times
for ( int j=n-1; j>=0; j--) { --------> n+1 times
sum = sum + matrix[ i ][ j ]; ------> mn times
}
}

return sum; -------> 1 time
}

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

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