example consider the following codesum for ( = <=ni++for ( = <=nj++sum++what is the running time for this code fragmentclearly it takes longer to run when is larger the basic operation in this example is the increment operation for variable sum we can assume that incrementing takes constant timecall this time (we can ignore the time required to initialize sumand to increment the loop counters and in practicethese costs can safely be bundled into time the total number of increment operations is thuswe say that the running time is (nc the growth rate for an algorithm is the rate at which the cost of the algorithm grows as the size of its input grows figure shows graph for six equationseach meant to describe the running time for particular program or algorithm variety of growth rates representative of typical algorithms are shown the two equations labeled and are graphed by straight lines growth rate of cn (for any positive constantis often referred to as linear growth rate or running time this means that as the value of growsthe running time of the algorithm grows in the same proportion doubling the value of roughly doubles the running time an algorithm whose running-time equation has highest-order term containing factor of is said to have quadratic growth rate in figure the line labeled represents quadratic growth rate the line labeled represents an exponential growth rate this name comes from the fact that appears in the exponent the line labeled nis also growing exponentially as you can see from figure the difference between an algorithm whose running time has cost ( and another with cost ( becomes tremendous as grows for the algorithm with running time ( is already much slower this is despite the fact that has greater constant factor than comparing the two curves marked and shows that changing the constant factor for one of the equations only shifts the point at which the two curves cross for the algorithm with cost ( is slower than the algorithm with cost ( this graph also shows that the equation ( log grows somewhat more quickly than both ( and ( nbut not nearly so quickly as the equation ( for constants ab na grows faster than either logb or log nb finallyalgorithms with cost ( or (nnare prohibitively expensive for even modest values of note that for constants ab > an grows faster than nb