there are two nested for loopswhich are controlled by counters and jrespectively the body of the outer loopcontrolled by counter iis executed timesfor , thusstatements and [ia/( are executed times each this implies that these two statementsplus the incrementing and testing of counter icontribute number of primitive operations proportional to nthat iso(ntime the body of the inner loopwhich is controlled by counter jis executed timesdepending on the current value of the outer loop counter thusstatement [jin the inner loop is executed + times by recalling proposition we know that +nn( )/ which implies that the statement in the inner loop contributes ( time similar argument can be done for the primitive operations associated with the incrementing and testing counter jwhich also take ( )time the running time of algorithm prefixaverages is given by the sum of three terms the first and the second term are ( )and the third term is ( by simple application of proposition the running time of prefixaverages is ( linear-time algorithm in order to compute prefix averages more efficientlywe can observe that two consecutive averages [ and [iare similara[ ( [ [ [ ])/ [ ( [ [ [ [ ])/( if we denote with the prefix sum [ [ [ ]we can compute the prefix averages as [is /( it is easy to keep track of the current prefix sum while scanning array with loop we are now ready to present algorithm prefixaverages in code fragment code fragment algorithmprefix averages