Consider an algorithm that contains loops of the form: for (x = 1 through n ){
For (y = 1 through x){
For (z = 1 through 10){
Task T
} // end for
} // end for
} // end for
If task T requires t time units,the loop on y requires ______ time units.
A)10 * t
B)(10 * t)+ x
C)10 * t * x
D)t * x

Question

Quizplus · Accepted Answer

The outer loop runs for n times, and for each iteration, the middle loop runs x times. Inside these two loops, task T is executed 10*z times, where z runs from 1 to 10. Therefore, the total number of times task T is executed is:
n * (1 + 2 + ... + n) * 10 = n * (n + 1) / 2 * 10 = 5 * n * (n + 1)
It follows that the total time units required to execute task T is t * 5 * n * (n+1).
So, the loop on y requires 5 times more time units than task T, and it runs x times within each outer iteration. Thus, the loop on y requires 5 * t * x time units, which is equal to the choice C.

Consider an Algorithm That Contains Loops of the Form: for (X