algorithm analysis as an example of the typical kinds of analyses that are performedconsider the problem of downloading file over the internet suppose there is an initial -sec delay (to set up connection)after which the download proceeds at (bytes)/sec then it follows that if the file is megabytesthe time to download is described by the formula (nn/ this is linear function notice that the time to download , file ( , secis approximately (but not exactlytwice the time to download file ( secthis is typical of linear function noticealsothat if the speed of the connection doublesboth times decreasebut the , file still takes approximately twice the time to download as file this is the typical characteristic of linear-time algorithmsand it is the reason we write (no( )ignoring constant factors (although using big-theta would be more precisebig-oh answers are typically given observetoothat this behavior is not true of all algorithms for the first selection algorithm described in section the running time is controlled by the time it takes to perform sort for simple sorting algorithmsuch as the suggested bubble sortwhen the amount of input doublesthe running time increases by factor of four for large amounts of input this is because those algorithms are not linear insteadas we will see when we discuss sortingtrivial sorting algorithms are ( )or quadratic model in order to analyze algorithms in formal frameworkwe need model of computation our model is basically normal computer in which instructions are executed sequentially our model has the standard repertoire of simple instructionssuch as additionmultiplicationcomparisonand assignmentbutunlike the case with real computersit takes exactly one time unit to do anything (simpleto be reasonablewe will assume thatlike modern computerour model has fixed-size (say -bitintegers and no fancy operationssuch as matrix inversion or sortingwhich clearly cannot be done in one time unit we also assume infinite memory this model clearly has some weaknesses obviouslyin real lifenot all operations take exactly the same time in particularin our modelone disk reads counts the same as an additioneven though the addition is typically several orders of magnitude faster alsoby assuming infinite memorywe ignore the fact that the cost of memory access can increase when slower memory is used due to larger memory requirements what to analyze the most important resource to analyze is generally the running time several factors affect the running time of program somesuch as the compiler and computer usedare obviously beyond the scope of any theoretical modelsoalthough they are importantwe cannot deal with them here the other main factors are the algorithm used and the input to the algorithm typicallythe size of the input is the main consideration we define two functionstavg (nand tworst ( )as the average and worst-case running timerespectivelyused by an algorithm on input of size clearlytavg ( <tworst (nif there is more than one inputthese functions may have more than one argument