quadratic-time algorithm our first algorithm for computing prefix averagesnamed prefix average is shown in code fragment it computes every element of separatelyusing an inner loop to compute the partial sum def prefix average ( ) """return list such thatfor all ja[jequals average of [ ] [ "" len(screate new list of zeros [ for in range( ) total begin computing [ [ for in range( ) total + [ [jtotal ( + record the average return code fragment algorithm prefix average in order to analyze the prefix average algorithmwe consider the various steps that are executed the statementn len( )executes in constant timeas described at the beginning of section the statementa [ ncauses the creation and initialization of python list with length nand with all entries equal to zero this uses constant number of primitive operations per elementand thus runs in (ntime there are two nested for loopswhich are controlledrespectivelyby counters and the body of the outer loopcontrolled by counter jis executed timesfor thereforestatements total and [jtotal ( + are executed times each this implies that these two statementsplus the management of counter in the rangecontribute number of primitive operations proportional to nthat iso(ntime the body of the inner loopwhich is controlled by counter iis executed timesdepending on the current value of the outer loop counter thusstatement total + [ ]in the inner loopis executed times by recalling proposition we know that ( )/ which implies that the statement in the inner loop contributes ( time similar argument can be done for the primitive operations associated with maintaining counter iwhich also take ( time the running time of implementation prefix average is given by the sum of three terms the first and the second terms are ( )and the third term is ( by simple application of proposition the running time of prefix average is (