revisiting the problem of finding the maximum of sequence for our next examplewe revisit the find max algorithmgiven in code fragment on page for finding the largest value in sequence proposition on page claimed an (nrun-time for the find max algorithm consistent with our earlier analysis of syntax data[ ]the initialization uses ( time the loop executes timesand within each iterationit performs one comparison and possibly one assignment statement (as well as maintenance of the loop variablefinallywe note that the mechanism for enacting return statement in python uses ( time combining these stepswe have that the find max function runs in (ntime further analysis of the maximum-finding algorithm more interesting question about find max is how many times we might update the current "biggestvalue in the worst caseif the data is given to us in increasing orderthe biggest value is reassigned times but what if the input is given to us in random orderwith all orders equally likelywhat would be the expected number of times we update the biggest value in this caseto answer this questionnote that we update the current biggest in an iteration of the loop only if the current element is bigger than all the elements that precede it if the sequence is given to us in random orderthe probability that the jth element is the largest of the first elements is (assuming uniquenesshencethe expected number of times we update the biggest (including initializationis hn nj= jwhich is known as the nth harmonic number it turns out (see proposition that hn is (log nthereforethe expected number of times the biggest value is updated by find max on randomly ordered sequence is (log nprefix averages the next problem we consider is computing what are known as prefix averages of sequence of numbers namelygiven sequence consisting of numberswe want to compute sequence such that ajis the average of elements [ ]sj]for that isj aji= [ij+ computing prefix averages has many applications in economics and statistics for examplegiven the year-by-year returns of mutual fundordered from recent to pastan investor will typically want to see the fund' average annual returns for the most recent yearthe most recent three yearsthe most recent five yearsand so on likewisegiven stream of daily web usage logsa web site manager may wish to track average usage trends over various time periods we analyze three different implementations that solve this problem but with rather different running times