Assignment 5 - Complexity Analysis (due Friday, 10/23 at 11:55pm) For each snipp
ID: 674751 • Letter: A
Question
Assignment 5 - Complexity Analysis (due Friday, 10/23 at 11:55pm)
For each snippet 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.
You are welcome to submit your responses as text files or scanned images.
1.
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;
}
2.
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;
}
3.
for (int i=0; i<10; i++)
for (int j=0; j<n; j++)
cout << i << “,” << j << endl;
4.
for (int i=0; i<n; i++)
for (int j=0; j<n; j++)
cout << i << “,” << j << endl;
5.
for (int i=0; i<n; i++) //assume n is divisible by 2
for (j=n/2; j>i; j--)
sum = i+j;
6.
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
1.
double sum_triples(double array[], int n) {
//n: size of the array. Assume n is divisible by 3
double sum=0; // 1 (only one times)
for (int i=0; i<n; i=i+3) //log3(n)+1 (each iteration value of i becomes i+3 )
sum = sum + array[ i ]; //log3(n)
return sum; //1
}
2.
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) // log2(n) + 1 (total execution of loop will be log2(n))
sum = sum + i; //log2(n)
return sum; // 1 time
}
3.
for (int i=0; i<10; i++) // 10 times + 1 i.e 11 times (1 extra time before exiting the loop )
for (int j=0; j<n; j++) // (i * n) i.e (10 * n) times + 1 i.e (10*n+1) times(1 extra time before exiting the loop)
cout << i << “,” << j << endl; // (10 * n) times
4.
for (int i=0; i<n; i++) // n+1 (1 extra time before exiting the loop )
for (int j=0; j<n; j++) // n * (n+1) (1 extra time before exiting the loop )
cout << i << “,” << j << endl; // (n * n)
5.
for (int i=0; i<n; i++) //assume n is divisible by 2 // (n+1) times (1 extra time before exiting the loop )
for (j=n/2; j>i; j--) // (summation (n/2 - i)) ,where i=0 to n-1
sum = i+j; // (summation (n/2 - i)) ,where i=0 to n-1
6.
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 (1 extra time before exiting the loop )
for ( int j=n-1; j>=0; j--) { // n + 1 times (1 extra time before exiting the loop )
sum = sum + matrix[ i ][ j ]; // m * n times
}
}
return sum; // 1 time
}