initializing and returning array at the beginning and end can be done with constant number of primitive operations per elementand takes (ntime initializing variable at the beginning takes ( time there is single for loopwhich is controlled by counter the body of the loop is executed timesfor , thusstatements [iand [is/( are executed times each this implies that these two statements plus the incrementing and testing of counter contribute number of primitive operations proportional to nthat iso(ntime the running time of algorithm prefixaverages is given by the sum of three terms the first and the third term are ( )and the second term is ( by simple application of proposition the running time of prefixaverages is ( )which is much better than the quadratic-time algorithm prefixaverages recursive algorithm for computing powers as more interesting example of algorithm analysislet us consider the problem of raising number to an arbitrary nonnegative integern that iswe wish to compute the power function ( , )defined as ( ,nxn this function has an immediate recursive definition based on linear recursion