IN C++ For each sample of code given below, indicate precisely how many times ea
ID: 3859057 • Letter: I
Question
IN C++
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.
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;
}
Q2.
double sum_exponentials(int n){ //n is a power of 3, i.e., n=3^k or k=log n base 3
int sum=0;
for (int i=1; i<n; i=i*3)
sum = sum + i;
return sum;
}
Q3.
for (int i=0; i<n; i++) {
for (int j=n; j>=i; j--)
cout << i << “,” << j <<endl;
}
Q4.
for (int i=0; i<n; i++) { //assume n is divisible by 2 => n = 2*k
for (j=n/2; j>i; j--)
sum = i+j;
}
Q5.
//matrix multiplication of A[m][n] and B[n][p]. The product is saved into C[m][p].
void mult_matricies( double A[][n], double B[][p], double C[][p], int m, int n , int p ){
for (int i=0; i<m; i++) {
for (int j=0; j<p; j++){
C[i][j] = 0;
for ( int k=0; k<n; k++) {
C[i][j] += A[i][k] * B[k][j];
}//for-k
}//for-j
}//for-i
}
Explanation / Answer
Answer 1)
double sum=0; runs till 0 as it is initialization condition
for (int i=0; i<n; i=i+3) , i runs from 0 to n
sum = sum + array[ i ]; this line runs till n , as i runs from 0 to n, sum runs till n + n = 2n = O(n)
return sum; it runs in n times . So the total complexity of this program is O(n)
}
Answer 2)
double sum_exponentials(int n){ //n is a power of 3, i.e., n=3^k or k=log n base 3
int sum=0; this line runs one time as it is the initial condition of this piece of code.
for (int i=1; i<n; i=i*3) , Here i runs from 1 to logn base 3. Since the variable i i runs till n and each time it is multiplied with 3.
sum = sum + i; it runs till n times. Since i runs from i to n times , this line will be executed n times
return sum; this will be printed single time only.
}
Answer 3)
for (int i=0; i<n; i++) , Here the variable i runs from 0 to n ,so this line runs till n
{
for (int j=n; j>=i; j--), Since j = n , this line will execute n times
cout << i << “,” << j <<endl; , this line will be printed single time after the above conditions of for loops met.
}
Answer 4)
for (int i=0; i<n; i++) { //assume n is divisible by 2 => n = 2*k , this line runs from 0 to n , so this will run till n times
for (j=n/2; j>i; j--) , , Since division of n is done with 2 , so it will be distributed in two sub parts , hence it will execute logn to the base 2 times.
sum = i+j; , this statement will run n times , because i runs from 0 to n.