chap algorithm analysis (nn change / log nn -figure the increase in problem size that can be run in fixed period of time on computer that is ten times faster the first column lists the right-hand sides for each of the five growth rate equations of figure for the purpose of this examplearbitrarily assume that the old machine can run , basic operations in one hour the second column shows the maximum value for that can be run in , basic operations on the old machine the third column shows the value for the new maximum size for the problem that can be run in the same time on the new machine that is ten times faster variable is the greatest size for the problem that can run in , basic operations the fourth column shows how the size of changed to become on the new machine the fifth column shows the increase in the problem size as the ratio of to problem size (as proportion to the original sizegained by faster computer this relationship holds true regardless of the algorithm' growth rateconstant factors never affect the relative improvement gained by faster computer an algorithm with time equation ( does not receive nearly as great an improvement from the faster machine as an algorithm with linear growth rate instead of an improvement by factor of tenthe improvement is only the square root of that thusthe algorithm with higher growth rate not only solves smaller problem in given time in the first placeit also receives less of speedup from faster computer as computers get ever fasterthe disparity in problem sizes becomes ever greater the algorithm with growth rate ( log improves by greater amount than the one with quadratic growth ratebut not by as great an amount as the algorithms with linear growth rates note that something special happens in the case of the algorithm whose running time grows exponentially in figure the curve for the algorithm whose time is proportional to goes up very quickly in figure the increase in problem size on the machine ten times as fast is shown to be about (to be preciseit is log the increase in problem size for an algorithm with exponential growth rate is by constant additionnot by multiplicative factor because the old value of was the new problem size is if next year you buy another