Fundamentals of the Analysis of Algorithm Efficiency EXAMPLE 3 Compare the orders of growth of n! and 2. (We discussed this informally in Section 2.1.) Taking advantage of Stirling's formula, we get 2()" lim -lim lim 2xn 2 Thus, though 2" grows very fast,n! grows still faster. We can write symbolically that w! (2"); note, however, that while the big-Omega notation does not preclude the possibility that n! and 2" have the same order of growth, the limit computed here certainly does Basic Efficiency Classes Even though the efficiency analysis framework puts together all the functions whose orders of growth differ by a constant multiple, there are still infinitely many such classes. (For example, the exponential functions a" have different orders of growth for different values of base a.) Therefore, it may come as a surprise that the time efficiencies of a large number of algorithms fall into only a few classes These classes are listed in Table 2.2 in increasing order of their orders of growth, along with their names and a few comments You could raise a concern that classifying algorithms by their asymptotic eff- ciency would be of little practical use since the values of multiplicative constants are usually left unspecified. This leaves open the possibility of an algorithm in a worse efficiency class running faster than an algorithm in a better efficiency class for inputs of realistic sizes. For example, if the running time of one algorithm is while the running time of the other is 10', the cubic algorithm will outperform the quadratic algorithm unless n exceeds 10. A few such anomalies are indeed known. Fortunately, multiplicative constants usually do not differ that drastically. As a rule, you should expect an algorithm from a better asymptotic efficiency class to outperform an algorithm from a worse class even for moderately sized inputs This observation is especially true for an algorithm with a better than exponential running time versus an exponential (or worse) algorithm. Exercises 2.2 1. Use the most appropriate notation among 0. e. and 2 to indicate the time efficiency class of sequential search (see Section 2.1) a. in the worst case. b. in the best case. c. in the average case. 2. Use the informal definitions of 0.9. and to determine whether the follow- ing assertions are true or false. 2.2 Asymptotic Notations and Basic Efficiency Classes TABLE 2.2 Basic asymptotic efficiency classes Class 1 log " log 2 2 Name Comments 59 constant logarithmic linear linearithmic quadratic cubic exponential factorial Short of best-case efficiencies, very few reasonable examples can be given since an algorithm's running time typically goes to infinity when its input size grows infinitely large Typically, a result of cutting a problem's size by a constant factor on each iteration of the algorithm (see Section 4.4). Note that a logarithmic algorithm cannot take into account all its input or even a fixed fraction of it: any algorithm that does so will have at least linear running time. Algorithms that scan a list of size (eg, sequential search) belong to this class Many divide-and-conquer algorithms (see Chapter 5). including mergesort and quicksort in the average case, fall into this category. Typically, characterizes efficiency of algorithms with two embedded loops (see the next section). Elemen tary sorting algorithms and certain operations on x matrices are standard examples Typically, characterizes efficiency of algorithms with three embedded loops (see the next section). Several nontrivial algorithms from linear algebra fall into this class Typical for algorithms that generate all subsets of an -element set. Often, the term "exponential" is used in a broader sense to include this and larger orders of growth as well. Typical for algorithms that generate all permutations of an n-element set. an(n+1)/2e O(n) b. nin+1)/2 On) c. (n+1)/2 ein) d. (n+1)/2 22(n) 3. For each of the following functions, indicate the class (g(n)) the function belongs to. (Use the simplest g(n) possible in your answers) Prove your assertions (2+1)10 c. 2n lgin + 2)+(x+2) Ig e. [log] b. 10m+7+3 2+1+3-1