running time linear ( log quadratic cubic input size (nfigure plot ( vs timeof various algorithms growth rates are still evident although the graph for the ( log nseems linearit is easy to verify that it is not by using straightedge (or piece of paperalthough the graph for the (nalgorithm seems constantthis is only because for small values of nthe constant term is larger than the linear term figure shows the performance for larger values it dramatically illustrates how useless inefficient algorithms are for even moderately large amounts of input running-time calculations there are several ways to estimate the running time of program the previous table was obtained empirically if two programs are expected to take similar timesprobably the best way to decide which is faster is to code them both and run themgenerallythere are several algorithmic ideasand we would like to eliminate the bad ones earlyso an analysis is usually required furthermorethe ability to do an analysis usually provides insight into designing efficient algorithms the analysis also generally pinpoints the bottleneckswhich are worth coding carefully to simplify the analysiswe will adopt the convention that there are no particular units of time thuswe throw away leading constants we will also throw away loworder termsso what we are essentially doing is computing big-oh running time since big-oh is an upper boundwe must be careful never to underestimate the running time of the program in effectthe answer provided is guarantee that the program will terminate within certain time period the program may stop earlier than thisbut never later