in our first two algorithmsthe prefix sum is computed anew for each value of that contributed ojtime for each jleading to the quadratic behavior in algorithm prefix average we maintain the current prefix sum dynamicallyeffectively computing [ [ sjas total [ ]where value total is equal to the sum [ [ sj computed by the previous pass of the loop over the analysis of the running time of algorithm prefix average followsinitializing variables and total uses ( time initializing the list uses (ntime there is single for loopwhich is controlled by counter the maintenance of that counter by the range iterator contributes total of (ntime the body of the loop is executed timesfor thusstatements total + [jand [jtotal ( + are executed times each since each of these statements uses ( time per iterationtheir overall contribution is (ntime the running time of algorithm prefix average is given by the sum of the four terms the first is ( and the remaining three are (nby simple application of proposition the running time of prefix average is ( )which is much better than the quadratic time of algorithms prefix average and prefix average three-way set disjointness suppose we are given three sequences of numbersaband we will assume that no individual sequence contains duplicate valuesbut that there may be some numbers that are in two or three of the sequences the three-way set disjointness problem is to determine if the intersection of the three sequences is emptynamelythat there is no element such that ax band simple python function to determine this property is given in code fragment def disjoint (abc) """return true if there is no element common to all three lists "" for in for in for in if = = return false we found common value return true if we reach thissets are disjoint code fragment algorithm disjoint for testing three-way set disjointness this simple algorithm loops through each possible triple of values from the three sets to see if those values are equivalent if each of the original sets has size nthen the worst-case running time of this function is (