algorithm analysis expectedit might be silly to expend great deal of effort to design clever algorithm on the other handthere is large market these days for rewriting programs that were written five years ago based on no-longer-valid assumption of small input size these programs are now too slow because they used poor algorithms for large amounts of inputalgorithm is clearly the best choice (although algorithm is still usablesecondthe times given do not include the time required to read the input for algorithm the time merely to read the input from disk is likely to be an order of magnitude larger than the time required to solve the problem this is typical of many efficient algorithms reading the data is generally the bottleneckonce the data are readthe problem can be solved quickly for inefficient algorithms this is not trueand significant computer resources must be used thusit is important thatwhenever possiblealgorithms be efficient enough not to be the bottleneck of problem notice that for algorithm which is linearas the problem size increases by factor of so does the running time algorithm which is quadraticdoes not display this behaviora tenfold increase in input size yields roughly hundredfold ( increase in running time and algorithm which is cubicyields thousandfold ( increase in running time we would expect algorithm to take nearly , seconds (or two and half hoursto complete for , similarlywe would expect algorithm to take roughly seconds to complete for , , howeverit is possible that algorithm could take somewhat longer to complete due to the fact that , , could also yield slower memory accesses than , on modern computersdepending on the size of the memory cache figure shows the growth rates of the running times of the four algorithms even though this graph encompasses only values of ranging from to the relative linear ( log nquadratic cubic running time input size ( figure plot ( vs timeof various algorithms