G.1 Running Time

Yet another way to study an algorithm is to compute the running time of the algorithm purely as a function of the length of the input. Worst-case analysis considers the longest running time of all inputs of a particular length. Average-time analysis considers the average of all the running times of inputs of a particular length. The worst-case analysis is typically referred to as the running time of an algorithm.

Finding an expression for the exact running time is often difficult, but in most cases close estimations are possible. Asymptotic analysis provides the means of analyzing the running time of the algorithms for large inputs. As the lengths of the inputs become large, the high-order terms dominate the value of the expression and the low-order terms have little or no effect. Hence, a close approximation can be obtained only by considering the highest-order term in an expression. For example, the highest-order term of the function f( n) = 2 n ⁵ + 100 n ³ + 27 n + 2003 is 2 n ⁵. As n becomes large, disregarding the coefficient 2, the function f( n) behaves like n ⁵ and it is said that f( n) is asymptotically at most n ⁵. The following are some common definitions that are useful in analyzing the asymptotic behavior of functions and hence algorithms.