problem but have rather different running times the problem we are interested in is the one of computing the so-called prefix averages of sequence of numbers namelygiven an array storing numberswe want to compute an array such that [iis the average of elements [ ] [ ]for that iscomputing prefix averages has many applications in economics and statistics for examplegiven the year-by-year returns of mutual fundan investor will typically want to see the fund' average annual returns for the last yearthe last three yearsthe last five yearsand the last ten years likewisegiven stream of daily web usage logsa web site manager may wish to track average usage trends over various time periods quadratic-time algorithm our first algorithm for the prefix averages problemcalled prefixaverages is shown in code fragment it computes every element of separatelyfollowing the definition code fragment algorithm prefixaverages let us analyze the prefixaverages algorithm initializing and returning array at the beginning and end can be done with constant number of primitive operations per elementand takes (ntime