For each sample of code given below, indicate precisely how many times each line
ID: 3859069 • Letter: F
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. Wirte out only how many times it will run. Eg ( n+1) times or n(n+1)/2 times.
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;
}
Explanation / Answer
3) (n+1) + n + (n-1) + (n-2) + (n-3) + .......+ 2 // outer loop will run n times and inner loop depends on value of i
= (n(n+1)/2) + n
= n ( 1 + (n+1)/2 )
= n(n+3)/2 times
4) (n/2) + ((n/2)-1) + ((n/2)-2) + ((n/2)-3) + ...+ ((n/2) - ((n/2)-1)) // Outer loop runs n times and inner loop depends on the value of i
= (n/2) (n/2) - [ 1+2+3+4+...+((n/2)-1)]
=(n/2)(n/2) - ((n/2)-1)(n/2)/2
=(n/2)[ (n/2) -( (n/2) -1)/2]
=(n/2)[ (n/2) -( (n/2) -1)/2]
=(n/2) [ 2*(n/2) -(n/2) +1]/2
=(n/2)[(n/2)+1]/2
=(n/2)[(n+3)/2]/2
=(n/2)(n+3)/4
=n(n+3)/8 times
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.